每日OJ题_完全背包④_力扣279. 完全平方数（一维和二维）

目录

力扣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. 情况一：拆出来一个 1 ，然后看看 11 的最小数量，记为 x1 ；
2. 情况二：拆出来一个 4 ，然后看看 8 的最小数量，记为 x2 ；（为什么拆出来 4 ， 而不拆出来 2 呢？）
3. 情况三：拆出来一个 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];}
};