322 - Coin Change

解法一 - DP

dp[i][amount] = 使用 coin 0-i，組出 amount 最少需要幾個 coin

dp[i][amount] = min(dp[i-1][amount], dp[i][amount-coins[i]]+1)

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n, vector<int>(amount+1, INT_MAX));

// Init
for(int c=0; c<n; c++)
dp[c][0] = 0;

// Build DP table
for(int c=0; c<coins.size(); c++) {
for(int a=1; a<=amount; a++) {
if(c > 0) {
dp[c][a] = dp[c-1][a];
}
if(a >= coins[c]) {
// If dp[c][a-coins[c]] == INT_MAX
// There's no way to use coin i to make up a
if(dp[c][a-coins[c]] != INT_MAX) {
dp[c][a] = min(dp[c][a], dp[c][a-coins[c]]+1);
}
}
}
}

return dp[n-1][amount] == INT_MAX ? -1 : dp[n-1][amount];
}
};

解法二 - 優化版 DP

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount+1, INT_MAX);

dp[0] = 0;

for(int c=0; c<coins.size(); c++) {
for(int a=1; a<=amount; a++) {
if(a >= coins[c]) {
if(dp[a-coins[c]] != INT_MAX) {
dp[a] = min(dp[a], dp[a-coins[c]]+1);
}
}
}
}

return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};