LintCode 完美平方题目分析代码

public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        for(int i=0;i*i<=n;i++) {
            dp[i*i] = 1;
        }
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j*j<=i;j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }

        return dp[n];
    }
}