- 比較「每個硬幣的面額」與「其次小硬幣的面額」
- 【情況1】硬幣有：$50, $10, $5, $1 四種面額，
- 【情況2】硬幣有：$10, $8, $1 三種面額，
- $10 < 2 * $8，不能貪心。
- 改用DP考慮全部條件，因為有些情況下，每次採取當下的最佳解，不一定是全面的最佳解。
- 【例子】$16 = $8 + $8 = $10 + $1 + $1 + $1 + $1 + $1 + $1
【題型1】Greedy
- 【範例】LeetCode 860. Lemonade Change
- 硬幣有：$20, $10, $5 三種面額，且 $20 >= 2 * $10，$10 >= 2 * $5，可以貪心。
- 盡可能從面額較大的硬幣開始使用。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int coins[] = {0, 0, 0}; //$20, $10, $5
for (int i=0; i<bills.size(); i++){
if (bills[i] == 20){
coins[0]++;
if (coins[1] > 0 && coins[2] > 0){
coins[1]--;
coins[2]--;
} else if (coins[2] >= 3){
coins[2] -= 3;
} else return false;
} else if (bills[i] == 10){
coins[1]++;
if (coins[2] > 0){
coins[2]--;
} else return false;
} else {
coins[2]++;
}
}
return true;
}
};
【題型2】DP
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int dp[amount+1];
memset(dp, 0x3F, sizeof(dp));
dp[0] = 0;
for (int i=0; i<coins.size(); i++){
for (int j=coins[i]; j<=amount; j++){
dp[j] = min(dp[j], dp[j-coins[i]]+1);
}
}
if (dp[amount] < 0x3F3F3F3F) return dp[amount];
else return -1;
}
};
Post Views (since April 2021) : 3,085