本文主要是介绍518. Coin Change 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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 位符号整数
解法一：
// 回溯。超时。
class Solution {
public:void change(int amount, const vector<int>& coins, int index, int& count) {// assert(amount >= 0);if (amount == 0) {++count;return;}if (index == coins.size()) return;int maxC = amount / coins[index];for (int i = 0; i <= maxC; ++i) {change(amount - i * coins[index], coins, index + 1, count);}}int change(int amount, vector<int>& coins) {int count = 0;change(amount, coins, 0, count);return count;}
};解法二：
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int c : coins) {for (int i = c; i <= amount; ++i) {dp[i] += dp[i - c];}}return dp[amount];}
};解法一：
回溯查找所有情况。超时。
解法二：
假设目前已知n（n>0）个硬币，要兑换的钱数为amount = i时的总情况数为dp[i]。dp[0] = 0。
此时如果再添一种面额为x的新硬币，它只可能会对原有dp数组中i>=x的元素产生影响。
具体的影响是；dp[i] += dp[i - x]，其中i>=x。
这个就是它的递推关系式。从0个硬币开始，初始时dp[0]=0。依次添加硬币，对每次添加对dp[]产生的影响进行更新。直到最终添加完所有硬币。
2020/07/04 11:55
这篇关于518. Coin Change 2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
