- 比較「每個硬幣的面額」與「其次小硬幣的面額」
- 【情況1】硬幣有：$50, $10, $5, $1 四種面額，
- $50 >= 2 * $10，可以貪心。
- 【情況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
- 【範例】LeetCode 322. Coin Change
- dp[ x ]：紀錄目前要湊成金額 x 的最少硬幣數目。
- 測試每個硬幣面額coins[ i ]
- 狀態轉移方程：當採用一個新的硬幣面額可以使用更少的硬幣數目來湊成金額 j 時，更新 dp[ j ] = min( dp[ j ], dp[ j – coins[ i ]] + 1);
- 【更多練習】ZeroJudge d133: 00357 – Let Me Count The Ways
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;
}
};