目录
力扣279. 完全平方数
问题解析
解析代码
优化代码（相同子问题分析和滚动数组）
力扣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 <= 10^4
class Solution {
public:
int numSquares(int n) {
}
};问题解析
（优化代码部分放了分析一维空间的思路，这个普通思路就简单描述了）
状态表示： dp[i][j] 表示：从前i个完全平方数中挑选，总和正好等于j，所有选法中最小的数量。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。但是最后一个物品能选很多个，因此需要分很多情况：
- 选 0 个i * i：dp[i][j] = dp[i - 1][j]
- 选 1 个i * i：dp[i][j] = dp[i - 1][j - i * i] + 1 ;
- 选 2 个i * i：dp[i][j] = dp[i - 1][j - 2 * i * i] + 2 ;
- ......
综上，状态转移方程为：
dp[i][j] = min(dp[i - 1][j] , dp[i - 1][j - i * i] + 1 + dp[i - 1][j - 2 * i * i] + 2 , ......)
这时发现，计算一个状态的时候，需要一个循环才能搞定的时候，我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态，通常就是用数学的方式做一下等价替换。
发现第二维是有规律的变化的，因此去看看 dp[i][j - i * i] + 1 ; 这个状态： dp[i][j - i * i] + 1 = min( dp[i - 1][j - 2 * i * i] + 2 , dp[i - 1][j - 3 * i * i] + 3 , ......)
因此可以修改我们的状态转移方程为： dp[i][j] = min(dp[i - 1][j] , dp[i][j - i * i] + 1。（j >= i * i ）。有个技巧，就是相当于把第二种情况 dp[i - 1][j - i * i] + 1 里面的 i - 1 变成 i 即可。
初始化： 初始化第一行即可，dp[0[0]为1，第一行后面初始化成无穷大。
填表顺序： 根据状态转移方程，仅需从上往下填表。
返回值： 根据状态表示，返回 dp[根号n][n] 。
解析代码
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> dp(amount + 1, 0); // 滚动数组优化
dp[0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = coins[i - 1]; j <= amount; ++j)
{
dp[j] = dp[j] + dp[j - coins[i - 1]];
}
}
return dp[amount];
}
};优化代码（相同子问题分析和滚动数组）
先看能不能将问题转化成我们熟悉的题型。这里给出一个用拆分出相同子问题的方式，定义一个状态表示。（得到的结果 i 和 j 换一下就是滚动数组优化的结果）
为了叙述方便，把和为 n 的完全平方数的最少数量简称为最小数量。
对于 12 这个数，分析一下如何求它的最小数量。
- 如果 12 本身就是完全平方数，就不用算了，直接返回 1 ;
- 但是 12 不是完全平方数，试着把问题分解⼀下：
- 情况一：拆出来一个 1 ，然后看看 11 的最小数量，记为 x1 ；
- 情况二：拆出来一个 4 ，然后看看 8 的最小数量，记为 x2 ；（为什么拆出来 4 ， 而不拆出来 2 呢？）
- 情况三：拆出来一个 8 ...... 其中，接下来求 11、8 的时候，其实又回到了原来的问题上。
因此，可以尝试用 dp 的策略，将 1 2 3 4 6 等等这些数的最小数量依次保存起来。再求较大的 n 的时候，直接查表，然后找出最小数量。
状态表示： dp[i] 表示：和为 i 的完全平方数的最少数量。
状态转移方程：
对于 dp[i] ，根据思路里的分析知道，可以根据小于等于 i 的所有完全平方数 x 进行划分：
- x = 1 时，最小数量为： 1 + dp[i - 1] ；
- x = 4 时，最小数量为： 1 + dp[i - 4] ......
为了方便枚举完全平方数，采用的策略： for(int j = 1; j * j <= i; j++)
综上，状态转移方程为：
dp[i] = min(dp[i], dp[i - j * j] + 1)
初始化：当 n = 0 的时候，没法拆分，结果为 0 ； 当 n = 1 的时候，结果为 1 。
填表顺序： 根据状态转移方程，仅需从左往右填表。
返回值： 根据状态表示，返回 dp[n] 。
class Solution {
public:
int numSquares(int n) {
// dp[i] 表示：和为 i 的完全平方数的最少数量
int m = sqrt(n);
vector<int> dp(n + 1, 0x3f3f3f3f);
dp[0] = 0;
for(int i = 1; i <= m; ++i)
{
for(int j = i * i; j <= n; ++j)
{
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};
