目录
力扣322. 零钱兑换
问题解析
解析代码
优化代码（滚动数组）
力扣322. 零钱兑换
322. 零钱兑换
难度 中等
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3 输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
}
};问题解析
先看能不能将问题转化成我们熟悉的题型。
- 在一些物品中挑选一些出来，然后在满足某个限定条件下，解决一些问题，大概率是背包模型；
- 由于每一个物品都是无限多个的，因此是一个完全背包问题。接下来的分析就是基于完全背包的方式来
状态表示： dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于 j ，所有的选法中，最少的硬币个 数。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。但是最后一个物品能选很多个，因此需要分很多情况：
- 选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。 此时最少的硬币个数为 dp[i - 1][j]
- 选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - v[i] 。因为挑选了一个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - coins[i]] + 1 ;
- 选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - 2 * coins[i]] + 2 ;
- ......
综上，状态转移方程为：
dp[i][j]=min(dp[i - 1][j], dp[i - 1][j - coins[i]] + 1, dp[i - 1][j - 2*coins[i]] + 2 ......)
这时发现，计算一个状态的时候，需要一个循环才能搞定的时候，我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态，通常就是用数学的方式做一下等价替换。
发现第二维是有规律的变化的，因此去看看 dp[i][j - v[i]] 这个状态： dp[i][j - v[i]]=min(dp[i - 1][j - coins[i]] + 1,dp[i - 1][j - 2*coins[i]]] + 2,dp[i - 1] [j - 3*coins[i]] + 3......)
因此可以修改我们的状态转移方程为： dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。（j >= coins[i] ， dp[i][j - coins[i]] 存在 。）（如果初始化多开一行一列，找coins数组要减一）
有个技巧，就是相当于把第二种情况 dp[i - 1][j - coins[i]] + 1 ⾥ ⾯的 i - 1 变成 i 即可。
初始化： dp[0[0]为0，初始化第一行即可。 这里因为取 min ，所以可以把无效的地方设置成无穷大 （0x3f3f3f3f） 因为这里要求正好凑成总和为 j ，因此，需要把第一行除了第一个位置的元素，都设置成无穷大。
填表顺序： 根据状态转移方程，仅需从上往下填表。
返回值： 根据状态表示，返回 dp[n][amount] 。由于最后可能凑不成总数为 amount 的情况，因此返回之前需要特判一下。
解析代码
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int INF = 0x3f3f3f3f; // 无穷大的一半
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));
// dp[i][j]表示：从前i个硬币中挑选，总和正好等于j，所有的选法中，最少的硬币个数
dp[0][0] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= amount; ++j)
{
if(j >= coins[i - 1])
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[n][amount] >= INF ? -1 : dp[n][amount];
}
};优化代码（滚动数组）
背包问题基本上都是利用滚动数组来做空间上的优化：
- 利用滚动数组优化。
- 直接在原始代码上修改。
在完全背包问题中，优化的结果为：
- 仅需删掉所有的横坐标。
（填一行数组的值的时候要用到前面新填的值，所以依旧是从左往右遍历，01背包是从右往左）
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int INF = 0x3f3f3f3f; // 无穷大的一半
int n = coins.size();
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = coins[i - 1]; j <= amount; ++j)
{
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
return dp[amount] >= INF ? -1 : dp[amount];
}
};
