[Vssue]0279.完全平方数.md

int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i * i <= n; i++) {
    for (int j = i * i; j <= n; j++) {
        dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
    }
}
return dp[n];

// 例: n = 5, dp = [0,MAX,MAX,MAX,MAX,MAX] 
i = 1:  j = 1: dp[1] = min(MAX, 0 + 1) = 1 (放1)
        j = 2: dp[2] = min(MAX, 1 + 1) = 2 (放1、1)
    j = 3: dp[3] = min(MAX, 2 + 1) = 3 (放1、1、1)
    j = 4: dp[4] = min(MAX, 3 + 1) = 4 (放1、1、1、1)
    j = 5: dp[5] = min(MAX, 4 + 1) = 5 (放1、1、1、1、1)
i = 2:  j = 4: dp[4] = min(4, 0 + 1) = 1 (放4)
    j = 5: dp[5] = min(5, 1 + 1) = 2 (放4、1)
// 最终结果 dp[5] = 2, 即 5 最少由两个完全平方数组成

youngyangyang04 / leetcode-master-comment

[Vssue]0279.完全平方数.md #163