279. Perfect Squares | LeetCode

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

• .
• , 因为n可以表示为n个1的平方和.
• 因为，其中. 则.
• 补充定义, 使得当n为完全平方数时，上面的等式依然成立。

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

当a在做遍历时，仅当发现更小的组合时，才更新的值。

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];        
}