【LeetCode每日一题】518. 零钱兑换 II
题目：
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
代码语言：javascript复制输入: 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:
代码语言：javascript复制输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
代码语言：javascript复制输入: amount = 10, coins = [10]
输出: 1
题解：
典型的背包问题，跟爬楼梯那道题非常相像。
代码语言：javascript复制class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount 1);
dp[0] = 1;
for (auto coin : coins) {
for (int j = 1; j <= amount; j ) {
if (j >= coin) {
dp[j] = dp[j] dp[j - coin];
}
}
}
return dp[amount];
}
};
