[DP]279. Perfect Squares

279. Perfect Squares

完美平方数都可以看做一个普通数加上一个完美平方数

如图所示，红色部分表示平方数，所有的完美平方数都可以看做一个普通数加上一个完美平方数，那么递推式就变为了：dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i<=n ;i++){
            dp[i] = i; // 最多都由1组成
            for(int j = 1; j*j<=i; j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}