279. 完全平方数 (opens new window)

1.动态规划

对于整数 i ，如果拆成两个数之和，那么 i 的完全平方数和的数量就等于两个加数的平方数数量之和，复用子问题的结果，所以本题考虑使用动态规划求解。

**定义dp[ i ]表示和为i的完全平方数的最小数量。**这里有一个小细节，内层循环的写法 j * j < = i ，可以将复杂度降到根号n。

class Solution {
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=i;
            for(int j=1;j*j<=i;j++){
                dp[i]=Math.min(1+dp[i-j*j],dp[i]);
            }
        }
        return dp[n];
    }
}