【筆記】DP:change coins (零錢問題)

  • 比較「每個硬幣的面額」與「其次小硬幣的面額」
  • 【情況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;
    }
};
分享本文 Share with friends