Description:
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer
Example:
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
Link:
https://leetcode.com/problems/coin-change-2/description/
解题方法：
这道题是一道背包问题，但是此题中因为不限制背包容量（即硬币没有限制多少个），所以很难理解。但是由我们可以从一个简单的角度去理解这道题的dp思想：
假设有硬币：1，2，5
当我们没有任何硬币时，从0到amount的组合数量为：
0 1 2 3 4 5 6 7 金额数
1 0 0 0 0 0 0 0 没有硬币时的组合方式
当我们有硬币1时，dp数组更新为：
0 1 2 3 4 5 6 7 金额数
1 0 0 0 0 0 0 0 没有硬币时的组合方式
1 1 1 1 1 1 1 1 有面额为1的硬币时
- 解释：需要组成1的钱数，我们可以从0的钱数得到，因为我们只需要加面额为1的硬币即可，从而从0到7我们都只有一种组合方式
当我们又多了硬币2时，dp数组更新为：
0 1 2 3 4 5 6 7 金额数
1 0 0 0 0 0 0 0 没有硬币时的组合方式
1 1 1 1 1 1 1 1 有面额为1的硬币时
1 1 2 2 3 3 4 4 有面额为1,2的硬币时
- 解释：当我们多了硬币2时，我们只需要管>=2的金钱数的更新，因为当金钱数少于面额2时，与硬币2毫无关系。那么当我们需要组成金钱数为2时，除了上一次我们可以用硬币1从金额1组成金额2（要组成金额1，我们只有一种方法），我们还可以从金额0直接用硬币2组成金额2（要组成金额0，我们只有一种方法），所以此时
组成金额2的方法=组成金额1的方法数+组成金额0的方法数，依次类推。
接下来的dp数组继续更新：
0 1 2 3 4 5 6 7 金额数
1 0 0 0 0 0 0 0 没有硬币时的组合方式
1 1 1 1 1 1 1 1 有面额为1的硬币时
1 1 2 2 3 3 4 4 有面额为1,2的硬币时
1 1 2 2 3 4 5 6 有面额为1,2,5的硬币时
Time Complexity：
O(MN) M为金额数 N为硬币种类
完整代码：
int change(int amount, vector<int>& coins)
{
if(amount == 0)
return 1;
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for(int i: coins)
for(int j = i; j <= amount; j++)
dp[j] += dp[j - i];
return dp[amount];
}
