279. Perfect Squares

完美平方數都可以看做一個普通數加上一個完美平方數

如圖所示，紅色部分表示平方數，所有的完美平方數都可以看做一個普通數加上一個完美平方數，那么遞推式就變?yōu)榱耍篸p[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];
    }
}