LeetCode 完全背包 279. 完全平方数
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
题解
由题可知，对于任意 n ，我们最大可以选择是数是 k=(int)sqrt(n)
题目转换过来就是从 1 到 k 之间选择任意个数（可以重复），使得其平方之和为 n ，求所有可能组合中最少需要多少个数字
这么一看题目就是完全背包问题了
我们定义 dp[ i ][ j ] 表示从 0 到 i 之间进行选择得到平方和为 j 的最少数字个数
对于任意 dp[ i ][ j ]，我们分为两种情况
- 不能选择数字 i，i * i>j
那么 dp[ i ][ j ]=dp[ i-1 ][ j ] - 可以选择数字 i，i * i<j
那么答案是选择和不选择之间小的那个
dp[ i ][ j ]=min(dp[ i-1 ][ j ]，dp[ i ][ j-i * i ]+1)
然后我们初始化 dp[ 1 ][ j ]
接着从 dp[ 1 ][ 0 ] 遍历数组即可
最后答案为 dp[ k ][ n ]
代码如下↓
class Solution {
public:int numSquares(int n) {int k=sqrt(n);vector<vector<int>> arr(k+1,vector<int>(n+1,0));for(int i=0;i<=n;i++){arr[1][i]=i;}for(int i=2;i<=k;i++){for(int j=1;j<=n;j++){if(i*i>j){arr[i][j]=arr[i-1][j];}else{arr[i][j]=min(arr[i-1][j],arr[i][j-i*i]+1);}}}return arr[k][n];}
};
空间优化
根据 dp[ i ][ j ]=min(dp[ i-1 ][ j ]，dp[ i ][ j-i * i ]+1) 我么发现我们要求的值仅与上一行有关
那么不妨将它们都放到一行里
dp[ j ]=min(dp[ j ]，dp[ j-ii ]+1) （前面的dp[ j ]是dp[ i ][ j ]，后面的是dp[ i-1 ][ j ]，上一行的，dp[ j-ii ]是dp[ i ][ j-i*i ]）
对于我们要求的dp[ j ]，其与上一行的dp[ j ]和同一行的dp[ j-i*i ]有关
在求值的过程中，dp[ j ]就是上一行的值
而dp[ j-i * i ]，也就是前面的值需要是同一行的
那么我们正好顺序遍历，前面的值都是更新过的，这一行的值
代码如下↓
class Solution {
public:int numSquares(int n) {int k=sqrt(n);vector<int> arr(n+1,0x3f3f3f3f);arr[0]=0;for(int i=1;i<=k;i++){for(int j=i*i;j<=n;j++){arr[j]=min(arr[j],arr[j-i*i]+1);}}return arr[n];}
};