# 518 - Coin Change 2

## 解法一 - 暴力法

``````class Solution {
public:
int change(int amount, vector<int>& coins) {
return enumerate(amount, coins, 0);
}

private:
int enumerate(int amount, vector<int>& coins, int curIdx){
if(amount == 0)
return 1;

if(coins.empty() || curIdx >= coins.size())
return 0;

// Use the coin[i]
int way1 = 0;
if(coins[curIdx] <= amount)
way1 = enumerate(amount-coins[curIdx], coins, curIdx);

// Do not use coin[i]
int way2 = enumerate(amount, coins, curIdx+1);

return way1+way2;
}
};
``````

## 解法二 - 暴力法 + memoization

``````class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<vector<int>> memo(coins.size(), vector<int>(amount+1, -1));
return enumerate(amount, coins, 0, memo);
}

private:
int enumerate(int amount, vector<int>& coins, int curIdx, vector<vector<int>>& memo){
if(amount == 0)
return 1;

if(coins.empty() || curIdx >= coins.size())
return 0;

if(memo[curIdx][amount] != -1)
return memo[curIdx][amount];

// Use the coin[i]
int way1 = 0;
if(coins[curIdx] <= amount)
way1 = enumerate(amount-coins[curIdx], coins, curIdx, memo);

// Do not use coin[i]
int way2 = enumerate(amount, coins, curIdx+1, memo);

memo[curIdx][amount] = way1+way2;
return memo[curIdx][amount];
}
};
``````

Runtime: 68 ms, faster than 10.27% of C++ online submissions for Coin Change 2. Memory Usage: 22.5 MB, less than 14.29% of C++ online submissions for Coin Change 2.

## 解法三 - DP

`dp[i][amount] = 使用 coin 0-i，組出 amount 有幾種方法`

`dp[i][amount] = dp[i-1][amount] + dp[i][amount-coins[i]]`

``````class Solution {
public:
int change(int amount, vector<int>& coins) {
if(coins.empty() && amount <= 0)
return 1;

if(amount > 0 && coins.empty())
return 0;

// Init
// amount == 0, there's one way to have this amount
vector<vector<int>> dp(coins.size(), vector<int>(amount+1, 0));
for(int c=0; c<coins.size(); c++)
dp[c][0] = 1;

// only one coin, when the amount is divisible by coin[0], there's one way
for(int a=0; a<=amount; a++)
dp[0][a] = (a%coins[0] == 0) ? 1 : 0;

// Building DP table
for(int c=1; c<coins.size(); c++) {
for(int a=1; a<=amount; a++) {
dp[c][a] = dp[c-1][a] + (coins[c] <= a ? dp[c][a-coins[c]] : 0);
}
}

return dp[coins.size()-1][amount];
}
};
``````

## 解法四 - 優化成只用一個 row 的 DP

`dp[i][amount] = dp[i-1][amount] + dp[i][amount-coins[i]]`

``````class Solution {
public:
int change(int amount, vector<int>& coins) {
if(coins.empty() && amount <= 0)
return 1;

if(amount > 0 && coins.empty())
return 0;

// Init
// amount == 0, there's one way to have this amount
vector<int> dp(amount+1, 0);
dp[0] = 1;

// Building DP table
for(int c=0; c<coins.size(); c++) {
for(int a=0; a<=amount; a++) {
dp[a] = dp[a] + (coins[c] <= a ? dp[a-coins[c]] : 0);
}
}

return dp[amount];
}
};
``````

Runtime: 12 ms, faster than 47.66% of C++ online submissions for Coin Change 2. Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Coin Change 2.