279. Perfect Squares

/*
Dynamic Programming
Time Complexity: O(sqrt(1) + sqrt(2) + sqrt(3) + ... + sqrt(n))
Space Complexity: O(n)
*/
class Solution {
    public int numSquares(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int[] dp = new int[n+1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int minCount = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minCount = Math.min(minCount, dp[i - j*j] + 1);
            }
            dp[i] = minCount;
        }

        return dp[n];
    }
}