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

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a 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

 

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

• the answer is guaranteed to fit into signed 32-bit integer

A:

首先 backtracking.  回溯。

class Solution {

public:

int change(int amount, vector<int>& coins) {

int res = 0;

helper(amount, coins, 0, res);

return res;

}

private:

void helper(int amount, const vector<int>& coins, int start, int& res) {

if (amount == 0) {

++res;

return;

}

if (start >= coins.size())

return;

for (int i = 0; i * coins[start] <= amount; i++) {

helper(amount - i * coins[start], coins, start + 1, res);

}

}

};

Mistakes：

    C++ 中，每个变量都需要显式初始化。类似于上面的，不然就是会random value

上面的LTE了。  加上memorization. (但是这个就比较麻烦。 所以还是用bottom-up 方式

经典的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];
    }
};

NOTE:

might cause overflow, thus need : 

class Solution {

public:

int change(int amount, vector<int>& coins) {

vector<double> dp(amount + 1, 0);

dp[0] = 1; // amount is 0, we select no coins, which is also a way

// since this is no longer a yes or no question, we cannot directly go back and add

for(auto coin : coins){

for(int val = coin; val <= amount; val ++){

// originally, dp[val] is the value that NOT used coin at all

// then add the value that have include that coin before for dp[val-coin]

dp[val] += dp[val-coin];

}

}

return static_cast<int>(dp[amount]);

}

};