279 完全平方数
思路:完全背包应用,物品对应完全平方数i * i,容量对应和,weight[i]对应完全平方数i * i,value[i]对应个数1
i的范围为[1, sqrt(n)]
j的范围为[0, n]
注意初始化dp为INT_MAX,因为求的最小数量
class Solution {
public:
int numSquares(int n) {
int m = sqrt(n);
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
for(int i = 1; i <= m; i++)
dp[i][0] = 0;
for(int j = 1; j <= n; j++){
dp[1][j] = dp[1][j - 1] + 1;
}
for(int i = 2; i <= m; i++){
for(int j = 1; j <= n; j++){
if(j >= i * i){
dp[i][j] = min(dp[i - 1][j], dp[i][j - i * i] + 1);
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
};
由二维数组解法改编而成
dp[i - j * j]下标比dp[i]小,所以j可以从小到大遍历
这非常重要,这是和01背包问题的区别