Programming Skills: Coin Change 2

[Problem]
https://leetcode.com/problems/coin-change-2/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 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

中文翻譯:

給你'coins'陣列，代表你有哪些種類的coin可以使用。

然後給你'amount'，代表一個金額。

問你如果要用coins來組成amount，有多少種方式 ?

[Solution]

Dynamic Programming.
The number of ways to make up the amount with coins[1]~coin[n] is equal to
the number of ways to make up the amount without coin[n]
+
the number of ways to make up the amount with at least one coin[n]

1.The relation between original problem and sub-problem.
Let's say we have coin [1,2,5] and amount=12.
The number of ways to make up 12 by [1,2,5] can be separate into 2 mutually exclusive cases :
Case 1.Not allow to use coin '5'
This mean you can only use [1,2] to make up 12.
It becomes a smaller sub-problem "the number of ways to make up the 12 by [1,2]"
Case 2.Must use at least one coin '5'
We must use at least one '5' , the so remaining amount is 12-5=7.
It becomes a smaller sub-problem "the number of ways to make up the 7 by [1,2,5]"

Finally, the answer of original problem will be the sum of case1 and case2.

2.The base case

When the amount = 0, there is only 1 way.

So we can build up a 2D reference table, from smallest sub-problem "make up 0 by [1]" to "make up 12 by [1,2,5]".

Let's write the code :


class Solution {
public:
    int change(int amount, vector<int>& coins){
        vector<int> dpt(amount+1,0);
        dpt[0]=1;//base case
        for(auto c:coins){
            for(int a=c;a<=amount;a++){
                dpt[a]+=dpt[a-c];    
            }
        }
        return dpt[amount];
    }    
}