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的組合數(shù)量為：
0 1 2 3 4 5 6 7 金額數(shù)
1 0 0 0 0 0 0 0 沒有硬幣時的組合方式
當我們有硬幣1時，dp數(shù)組更新為：
0 1 2 3 4 5 6 7 金額數(shù)
1 0 0 0 0 0 0 0 沒有硬幣時的組合方式
1 1 1 1 1 1 1 1 有面額為1的硬幣時
- 解釋：需要組成1的錢數(shù)，我們可以從0的錢數(shù)得到史隆，因為我們只需要加面額為1的硬幣即可，從而從0到7我們都只有一種組合方式
當我們又多了硬幣2時曼验，dp數(shù)組更新為：
0 1 2 3 4 5 6 7 金額數(shù)
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的金錢數(shù)的更新，因為當金錢數(shù)少于面額2時鬓照，與硬幣2毫無關系熔酷。那么當我們需要組成金錢數(shù)為2時，除了上一次我們可以用硬幣1從金額1組成金額2（要組成金額1豺裆，我們只有一種方法）拒秘，我們還可以從金額0直接用硬幣2組成金額2（要組成金額0，我們只有一種方法），所以此時
組成金額2的方法=組成金額1的方法數(shù)+組成金額0的方法數(shù)躺酒，依次類推押蚤。
接下來的dp數(shù)組繼續(xù)更新：
0 1 2 3 4 5 6 7 金額數(shù)
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為金額數(shù) 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];
}
