iT邦幫忙

2

動態規劃經典題: 兩道換零錢問題

今天分享兩道換零錢的問題:
假設某一個國家的硬幣幣值有1元、2元、5元,
要湊到n元,
有兩種經典的問題,
一是問說最少要幾個硬幣可以湊到n元,
第二種是問說總共有幾種方式可以湊到n元?

你可以假設每種幣值使用數量都沒有限制,
比如說你去買一萬元的電視,
你拿10000個1元硬幣去付款也是OK的

換零錢(一)- 最少要幾個硬幣湊n元?

參考題目: Leetcode- 322. Coin Change
例子:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
說明: 11 = 5 + 5 + 1

譬如說用1元、2元、5元湊n元好了,
我們建一個表格DP[i]表示湊i元最少需要幾個硬幣,
表格大小為amount+1
初始值先設DP[0]=0
因為湊0元需要0個硬幣,
其它的DP[i]就先設成無限大

然後從coins裡面幣值最小的開始填表,
譬如本例的公式為
DP[i]= min(DP[i-1], DP[i-2], DP[i-5])+1
(general的情況請自行類推)

c++ 程式

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        long long inf = (long long)1<<32;
        vector<long long> DP(amount+1, inf);
        DP[0]=0;
        int min_coin = coins[0];
        for(int i = 1; i<coins.size(); i++){
             min_coin = min(coins[i], min_coin);
        }
        for(int i = min_coin; i<= amount; i++){
            long long min_way = inf;
            for(int coin: coins){
                if(i-coin>=0){
                    min_way = min(min_way, DP[i-coin]);
                }
            }
            DP[i] = min_way+1;
        }
        return DP[amount]<inf?DP[amount]:-1;
    }
};

python 程式 (我感覺此題python較容易寫)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        DP = [0] + [float('inf')] * amount
        for i in range(min(coins), amount+1):
            DP[i] = min([DP[i-x] for x in coins if i-x>=0])+1
        return DP[-1] if DP[-1]!=float('inf') else -1

換零錢(二)- 總共有幾種方式湊n元?

參考題目: Leetcode- 518. Coin Change 2
例子:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
說明: 有四種方式湊到5元:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

思路: 我們令DP[i][j]表示使用前i種銅版,湊j元有幾組解,
陣列DP的大小設(錢幣種類數量+1)*(欲湊金額數量+1)

初始值設DP[i][0] = 1; (因為我們設湊0元都是一種方法,就是不出錢)
對於j>1,如何用前i種硬幣湊出j元呢?
有兩種方式:

  • 不使用第i種錢,共DP[i-1][j]種可能
  • 在「第i種錢的幣值<=j的狀況下可以用第i種錢」,共DP[i][j-第i種錢的幣值]種可能

直接上程式碼比較清楚:

c++ 程式

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        
        //DP[i][j]表示使用前i種銅版,湊j元有幾組解
        vector<vector<int>> DP(coins.size()+1, vector<int>(amount+1,0));
        
        for(int i=0;i<DP.size();i++){
            DP[i][0] = 1; //湊0元都是一種方法
        }
        
        for(int i=1;i<DP.size();i++){
            for(int j=1;j<DP[0].size();j++){
                DP[i][j] = DP[i-1][j] + (coins[i-1]<=j?DP[i][j-coins[i-1]]:0);
            }
        }
        return DP[coins.size()][amount];
        
    }
};

python 程式

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # DP[i][j]表示使用前i種銅版,湊j元有幾組解
        DP = [[0]*(amount+1) for i in range(len(coins)+1)]
        
        for i in range(len(DP)):
            DP[i][0] = 1; #湊0元都是一種方法

        for i in range(1, len(DP)):
            for j in range(1, len(DP[0])):
                DP[i][j] = DP[i-1][j] + (DP[i][j-coins[i-1]] if coins[i-1]<=j else 0);
        return DP[len(coins)][amount];

<另解>
其實我們有更省空間的作法,直接令DP[i]為湊i元有幾組解就可以了,
每次加入一種新的硬幣去刷新表格,
想法大致同上:

c++ 程式

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        
        vector<int> DP(amount+1,0); //DP[i]湊i元有幾組解 
        DP[0] = 1; //湊0元為一種方法
        for(int coin: coins){
            for(int i=0; i<=amount;i++){
                if(i-coin>=0){
                    DP[i] += DP[i-coin];
                }
            }
        }
        return DP[amount];
    }
};

python 程式

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        DP = [1] + [0] * amount # DP[i]表示湊i元有幾組解(湊0元有一組解)
        for coin in coins:
            for i in range(amount+1):
                if i-coin>=0:
                    DP[i] += DP[i-coin]
        return DP[amount]

尚未有邦友留言

立即登入留言