零钱兑换问题
leetcode中有两个零钱兑换问题，在此汇总在一块统一分析。首先看第一个题目：
leetcode 322
解析：零钱兑换问题，给了一堆硬币和一个数值，要求计算出当前数组兑换成零钱的最小数量，如果无法兑换则返回-1。
思路：对于求极值问题，考虑动态规划思路。假设dp[i]表示数值i兑换成零钱后的最小数量，因为dp[0]=0，最终返回的结果为dp[amount]，因为申请的dp数组长度为amount+1。采用两层循环，外层i从1到amount，内存循环遍历零钱数组，如果当前零钱num小于i，表示i可以使用零钱num来兑换，因为此时dp[i]=dp[i-num]+1,因为需要选取最小值，所以dp[i]=min(dp[i],dp[i-num]+1)。通过递推关系也可以看出dp数组初始化时不能设置为INT_MAX，否则会超出，因此这里设置为amount+1。
思路总结如下：
先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount 。
然后确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。
然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins 中选择一个硬币，然后目标金额就会减少：
最后明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1。
PS：为啥dp数组初始化为amount + 1 呢，因为凑成amount 金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount + 1 就相当于初始化为正无穷，便于后续取最小值。
代码如下：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1, amount+1);
dp[0] = 0;
for(int i=1; i <= amount; i++)
{
for(auto num : coins)
{
if(num <= i)
{
dp[i] = min(dp[i], dp[i-num]+1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
详细分析参见：https://xianpengcui.com/2020/04/19/leetcode-322-coin-change/
https://mp.weixin.qq.com/s/Cw39C9MY9Wr2JlcvBQZMcA
第二个问题
leetcode 518
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0 .
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
Constraints:
- 1 <= coins.lengthh <= 300
- 1 <= coins[i] <= 5000
- All the values of coins are unique.
- 0 <= amount <= 5000
我们可以把这个问题转化为背包问题的描述形式：
有一个背包，最大容量为amount ，有一系列物品coins ，每个物品的重量为coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
解题思路：
这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。
第一步要明确两点，「状态」和「选择」。
这部分都是背包问题的老套路了，我还是啰嗦一下吧：
状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确dp数组的定义。
首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组。
dp[i][j]的定义如下：
若只使用前i个物品，当背包容量为j时，有dp[i][k]种方法可以装满背包。
换句话说，翻译回我们题目的意思就是：
若只使用coins中的前i个硬币的面值，若想凑出金额 j，有dp[i][j]种凑法。
经过以上的定义，可以得到：
base case 为dp[0][..] = 0, dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
我们最终想得到的答案就是dp[N][amount] ，其中N为coins数组的大小。
代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int len = coins.size();
vector<vector<int>> dp(len+1, vector<int>(amount+1, 0));
for(int i=0; i <= len; i++){
dp[i][0] = 1;
}
for(int i =1; i <= len; i++){
for(int j=1; j <= amount; j++){
if(j >= coins[i-1]){
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[len][amount];
}
};
而且，我们通过观察可以发现，dp数组的转移只和dp[i][..]和dp[i-1][..]有关，所以可以压缩状态，进一步降低算法的空间复杂度：
1.状态：dp[i]表示金额i的组成次数。很明显当amount=0时，dp[0] = 1；
2.动态方程：dp[i] = dp[i] + dp[i – coins[j]]；
代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0] = 1;
for(int coin : coins){
for(int j = coin; j <= amount; j++){
dp[j] = dp[j] + dp[j-coin];
}
}
return dp[amount];
}
};
参考：https://mp.weixin.qq.com/s/Cw39C9MY9Wr2JlcvBQZMcA
About Author
