题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
思路
动态规划，思考做出第一步的操作(枚举conins[i]的几种可能性)后，剩余的是什么子问题
对于任意dp[i][j]，我们依次从上到下，从左到右计算，dp[i][j]的值是下面的方法数的和：
0,完全不用arr[i]货币(即用0张arr[i]货币)，只使用arr[0..i-1]货币去凑剩下的钱j时，方法数为dp[i-1][j]
1,用1张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-arr[i]时，方法数为dp[i-1][j-arr[i]]
2,用2张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-2*arr[i]时，方法数为dp[i-1][j-2*arr[i]]
3,用3张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-3*arr[i]时，方法数为dp[i-1][j-3*arr[i]]
…
k,用k张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-k*arr[i]时，方法数为dp[i-1][j-k*arr[i]]
针对上面的情况，我们可以将从1到k的情况进行进一步的优化，
其实从1种情况到第k种情况方法的计数和就是dp[i][j-arr[i]]的定义中各种情况的计数之和：
0,完全不用arr[i]货币(即用0张arr[i]货币)，只使用arr[0..i-1]货币去凑剩下的钱j-arr[i]时，方法数为dp[i-1][j-arr[i]]
1,用1张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-arr[i]-arr[i]时，方法数为dp[i-1][j-arr[i]-arr[i]]=dp[i-1][j-2*arr[i]]
2,用2张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-arr[i]-2*arr[i]时，方法数为dp[i-1][j-arr[i]-2*arr[i]] =
dp[i-1][j-3*arr[i]]
…
k-1,用k张arr[i]货币，用arr[0..i-1]货币去凑剩下的钱j-arr[i]-(k-1)*arr[i]时，方法数为dp[i-1][j-arr[i]-(k-1)*arr[i]] =
dp[i-1][j-k*arr[i]]
dp[i][j-arr[i]]定义：
=
dp[i-1][j-arr[i]] + dp[i-1][j-arr[i]-arr[i]] + dp[i-1][j-arr[i]-2*arr[i]] + ... + dp[i-1][j-arr[i]-(k-1)*arr[i]]
=
dp[i-1][j-arr[i]] + dp[i-1][j-2*arr[i]] + dp[i-1][j-3*arr[i]] + dp[i-1][j-k*arr[i]]
代码实现1
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0)
return 1;//说明不用任何零钱就可以凑成amount，方法组合数为1，一种方法
int n = coins.size();
if(n == 0)
return 0;//如果没有硬币，那么我们凑成amount的方法数为0，没有任何方法能够凑成
vector<vector<int>> dp(n,vector<int>(amount+1,0));
for(int i=0;i<=amount;i++)//动态规划，初始化第一行
{
if(i%coins[0] == 0)
dp[0][i]=1;
}
for(int i = 1; i < n; i++)//一行一行的求递推公式
{
//根据递推公式我们也应该初始化成这个值
dp[i][0] = 1;
for(int j = 1; j <= amount; j++)
{
dp[i][j]= dp[i-1][j];//凑数方案中第i种硬币出现0次
//为了求总组合数，做到不重不漏，枚举划分方案中第i种硬币可以出现的次数
for(int cnt = 1;cnt*coins[i] <= j;cnt++)
dp[i][j] += dp[i-1][j-cnt*coins[i]];
}
}
return dp[n-1][amount];
}
};
代码实现2
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0)
return 1;//说明不用任何零钱就可以凑成amount，方法组合数为1，一种方法
int n = coins.size();
if(n == 0)
return 0;//如果没有硬币，那么我们凑成amount的方法数为0，没有任何方法能够凑成
vector<vector<int>> dp(n,vector<int>(amount+1,0));
for(int i=0;i<=amount;i++)//动态规划，初始化第一行
{
if(i%coins[0] == 0)
dp[0][i]=1;
}
for(int i = 1; i < n; i++)
{
//根据递推公式我们也应该初始化成这个值
dp[i][0] = 1;
for(int j = 1; j <= amount; j++)
{
dp[i][j]= dp[i-1][j];//凑数方案中第i种硬币出现0次
//为了做到不重不漏，枚举划分方案中第i种硬币可以出现的次数
// for(int cnt = 1;cnt*coins[i] <= j;cnt++)
// dp[i][j] += dp[i-1][j-cnt*coins[i]];
//对上面的枚举方案进行进一步的优化，
if(j-coins[i]>=0)
dp[i][j] += dp[i][j-coins[i]];
}
}
return dp[n-1][amount];
}
};
进一步的思考
根据上面的二维动态规划的递推公式：
dp[i][j]
=
dp[i-1][j] if j-coins[i] < 0
dp[i-1][j]+ dp[i][j-coins[i]] if j-coins[i]>=0
我们可以可以只用一维数组保存中间的信息
dp[j]
=
dp[j] if j-coins[i] < 0
dp[j]+ dp[j-coins[i]] if j-coins[i]>=0