6. 完全平方数（LeetCode-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 <= 104
思路
看到示例一的 4 + 4 + 4 4+4+44+4+4 知道是完全背包问题，本题求和为 n 的完全平方数的最少数量
五部曲
dp[j] 含义
和为 j的完全平方数的最少数量
递推公式
想一下，如果访问的当前物品是完全平方数，那么就分别求装它和不装它的数量，二者取小值。如果不是完全平方数，那么还是取不装它的数量
d p [ j ] = m i n ( d p [ j ] , d p [ j − i ] + 1 )
数组初始化
和为 0的完全平方数的最少数量肯定为零，而其他要初始化为最大值
遍历顺序
这里求最少数量，是组合数还是排列数都无所谓，所以顺序随意
代码展示
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { bool flag = false; if (i == 1) { flag = true; } for (int k = 0; k < i; k++) { if (k * k == i) { flag = true; break; } } for (int j = i; j <= n; j++) { if (flag && dp[j - i] != INT_MAX) { dp[j] = min(dp[j], dp[j - i] + 1); } } } return dp[n]; } };
分析一下，很快写出来了。但时间复杂度过于之高。那肯定是求完全平方数没有处理好。看了下题解，是我的物品选错了，我是遍历数然后判断它是不是完全平方数，但这样做就烦了。数值 n什么时候完全平方数？说白了 n是整数。那我的物品就取 n
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { for (int j = i * i; j <= n; j++) { dp[j] = min(dp[j], dp[j - i * i] + 1); } } return dp[n]; } };
