279. Perfect Squares

DP Solution

class Solution {
    public int numSquares(int n) {
        // base case must be dp[0]=0 not dp[1]=1;
        // dp[0] = 0;
        // dp[i] = min(dp[i-x^2])+1; (x = 0,1,2,...sqrt)
        int[] memo = new int[n+1];   
        
        for (int i=1; i<=n; i++){
            // the result won't be larger than i
            int min = i-1;
            int sqrt = (int) Math.sqrt(i);
            for(int j=1; j<=sqrt; j++){
                min = memo[i-j*j]<min? memo[i-j*j]: min;
            }
            memo[i] = min+1;
        }
        return memo[n];
    }
}