518. Coin Change 2 --------M ~~~~~

 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.

 

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

 

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

A:

经典的DP问题。  每次新增一个coin的值。 并对这个coin，用多个情况

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> preCoins(1+amount,0);
        preCoins[0] = 1;
        // each time, add a new denomination . and then split with how many this new coid used
        for(int i =0;i< coins.size();i++){
            int coin = coins[i];
            vector<int> includeNewCoin = preCoins; // initially without new-coin case
            for(int k = 1; k* coin <= amount; k++){
                for(int total = k * coin; total <=amount;total++){
                    includeNewCoin[total] += preCoins[total-k*coin];
                }
            }
            preCoins = includeNewCoin;
        }
        return preCoins[amount];
    }
};

Errors:

一开始没考虑amount == 0,  return should be 1.

改进：

我们采用的方法是一个硬币一个硬币的增加，每增加一个硬币，都从1遍历到 amount，对于遍历到的当前钱数j，组成方法就是不加上当前硬币的拼法 dp[i-1][j]，还要加上，去掉当前硬币值的钱数的组成方法，当然钱数j要大于当前硬币值，状态转移方程也在上面的分析中得到了：

dp[i][j] = dp[i - 1][j] + (j >= coins[i - 1] ? dp[i][j - coins[i - 1]] : 0)

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> V(1+amount,0);
        V[0] = 1;
        for(auto coin : coins){
            for(int i = coin; i<= amount;i++ )
                V[i] += V[i-coin]; //V[i] is for previous, without coin for i.   V[i-coin] is use current coid for i
        }
        return V[amount];
    }
};