Coin Change II

LeetCode #518

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:

if amount==0, 
Output: 1

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

Idea:

To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

用DP[m][amount]来memoization。

Code:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int m=coins.size();

        vector<vector<int>> DP(m, vector<int>(amount+1, -1));

        return DFS(coins, m-1, amount, DP);
    }

    int DFS(vector<int>& coins, int m, int amount, vector<vector<int>> & DP){
        if(amount==0){
            return 1;
        }
        if(m<0 || amount<0) return 0;

        if(DP[m][amount]!=-1) return DP[m][amount];

        DP[m][amount]=DFS(coins, m, amount-coins[m], DP)+DFS(coins, m-1, amount, DP);

        return DP[m][amount];
    }
};