题目
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
解题
这道DP题有两个思路：
1.这个题要的是给了硬币面值a1,a2,a3,...由给定的硬币组合成总金额的组合数，这个和爬楼梯很像，不过可以把爬楼梯看作是给定了两个固定的台阶数，1阶，2阶，问由给定的两种台阶数组合成总台阶数的排列数。
2.这是一个完全背包，给定了包的容量amount,以及n个物品，每个物品的重量是coins[i]，每个物品的数量无限，问最多存在几种能够恰好装满背包的方法。
思路1：
一维dp，改变循环顺序，组合数变成求排列数，排列数变成求组合数
（类似爬楼梯）求排列数：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+100];
dp[0] = 1;
for(int i=1;i<amount+100;i++) dp[i] = 0;
for(int i=1;i<=amount;i++)
{
for(int j=0;j<coins.size();j++)
{
if(i<coin) continue;
dp[i] = dp[i] + dp[i-coin[j]];
}
}
return dp[amount];
}
};
本题是求组合数，更换上面的循环顺序：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+100];
dp[0] = 1;
for(int i=1;i<amount+100;i++) dp[i] = 0;
for(int j=0;j<coins.size();j++)
{
int coin = coins[j];
for(int i=1;i<=amount;i++)
{
if(i<coin) continue;
dp[i] = dp[i] + dp[i-coin];
}
}
return dp[amount];
}
};
思路2：
base case:
(dp[0][cdot])= 0 如果不使用任何硬币面值，就无法凑出任何金额，即0种凑法 和 (dp[cdot][0])= 1 (dp[0][0]=1) 如果要凑出的目标金额为 0，那么有唯一的一种凑法
选择和状态：
1.选择: 装进背包 或 不装进背包
2.状态: 背包的容量 和 可选择的物品（有两个状态，所以dp用一个二维数组）
状态转移
(ullet) 如果把第i个物品装入背包(即使用coins[i]这个面值的硬币)，此时凑法dp[i][j]=dp[i][j-coins[i-1]] ；j-coins[i-1]表示当前背包的容量j减去当前i的重量coins[i-1];
(ullet) (因为i是从 1 开始的，所以coins的索引为i-1时表示第i个硬币的面值)
如果不把第i个物品装入背包(即不使用coins[i]这个面值的硬币)，此时凑法为dp[i][j]= dp[i-1][j]，表示和之前状态的结果一样。
// 当选择的第i个硬币的金额比想凑的金额大时，即只有选择不装
if (j - coins[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
// 我们要求的dp[i][j]是共有多少种凑法，所以dp[i][j]的值应该是以上两种选择的结果之和，dp[i][j] = 不装 + 装
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
}