完全平方数

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 10^4

解题思路

动态规划

完全背包问题，把物品看成完全平方数，物品可以重复使用，背包容量为n，问装满背包的最少物品数量

本题思路同[零钱兑换](./18. 零钱兑换.md)完全相同

1.确定dp数组及下标的含义

dp[j] 表示凑成和为 j 使用的最少完全平方数为dp[j]

2.确定递推公式

dp[j] 可以由dp[j - i * i] 得到，若考虑i * i，那么凑成和为 j 的最少平方数就为dp[j - i * i] + 1

而dp[j] 要取所有dp[j] 中的较小者

故递推公式为，dp[j] = Math.min(dp[j], dp[j - i * i] + 1)

3.初始化dp数组

非排列组合问题，dp[0] = 0，表示凑成和为0的平方数最少数量时0

对于非0下标，dp[j]必须初始化为一个最大值，否则再求最小值时会被0覆盖

只有dp[j - i * i]不为最大值时，才进行比较，因为最大值表示没有方案可以凑成j - i * i

4.确定遍历顺序

非排列组合问题，先遍历物品后遍历背包或先遍历背包后遍历物品都可以

这里选先遍历物品，后遍历背包，完全背包问题要从小到大遍历背包

代码

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        int max = Integer.MAX_VALUE;
        for(int i = 1; i < dp.length; i++){
            dp[i] = max;
        }
        for(int i = 1; i <= Math.sqrt(n); i++){//遍历物品
            for(int j = i*i ; j <= n ; j++){ //遍历背包
                if(dp[j - i*i] != max){
                    dp[j] = Math.min(dp[j], dp[j - i*i]+1);
                }
            }
        }
        return dp[n];
    }
}

• 时间复杂度：$O(n\times \sqrt n)$
• 空间复杂度：$O(n)$