279. Perfect Squares | LeetCode

定义 $dp[n]$ 为：n最少可由 $dp[n]$ 个完全平方数的和构成。所以，我们有：

$dp[1]=1$ .
$1 \leq dp[n] \leq n$ , 因为n可以表示为n个1的平方和.
因为 $n = a^2 + (n-a^2)$ ，其中 $0 \leq a \leq \sqrt{n}$ . 则 $dp[n] = \min_{0 \leq a \leq \sqrt{n}}{ 1 + dp[n-a^2]}$ .
补充定义 $dp[0]=0$ , 使得当n为完全平方数时，上面的等式依然成立。

稍微解释一下第三条。 $dp[n]$ 表示的是平方数的和。所以，组成它的和中，至少有一个元素是以平方的形式存在于等式中。这就是 $a^2$ 。此时，即便是n为完全平方数，由于我们有第一条补充定义 $dp[0]=0$ ，我们的等式依旧成立。

当a在 $[0, \sqrt{n}]$ 做遍历时，仅当发现更小的组合时，才更新 $dp[n]$ 的值。

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