Eisen 筆記

#322. Coin Change

題目描述

給你一個表示不同面額硬幣的整數陣列coins以及表示金額的整數amount。

回傳能夠湊成金額的最少硬幣數量。如果硬幣的組合無法湊成金額，回傳-1。

你可以假設每個面額的硬幣數量都是無限大。

限制條件

  1. 1 <= coins.length <= 12
  2. 1 <= coins[i] <= 231 - 1
  3. 0 <= amount <= 104

解題思路

Brute Force & Memorize

這一題要我們找出使用最少硬幣的組合，所以一開始挑選硬幣的時候應該要從最大的硬幣開始挑選，並且用目標金額減去選擇的硬幣面額。

當選完一個硬幣之後，下一次的選擇仍然會是所有的硬幣組合。

選完硬幣，並減去額度後會有三種結果：

  1. 金額為負：代表目前挑選的硬幣是不正確的，因此不用理會。
  2. 金額為零：代表組合順利完成，當前硬幣為最小的組合。
  3. 金額為正：代表需要繼續挑選硬幣，繼續挑選則會有另外兩種結果。
    1. 有組合存在：有組合存在，則根據當下的所有的硬幣挑選結果選出最小的組合結果。
    2. 沒有組合存在：則標示這個組合為錯誤組合。

這一輪的硬幣選擇結果全部都得出並且比較之後，就可以回傳這一輪的硬幣選擇中最小的結果。

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        Array.Sort(coins);
        return PickCoins(coins,amount,new Hashtable());        
    }
    public int PickCoins(int[] coins, int amount, Hashtable done){
		// 如果結果已存在，直接回傳結果
        if(done.Contains(amount)) return (int) done[amount];
		// 計算不同組合的結果
        int minComb = Int32.MaxValue;
        for(int i=coins.Length-1;i>=0;i--){
            int subVal = amount - coins[i];
			// 如果挑選硬幣後的結果已存在，與當前輪數的結果比較並且繼續計算其他挑選組合的結果。
            if(done.Contains(subVal)){
                int res = (int)done[subVal];
                if(res!=-1) minComb = Math.Min(minComb,res);                                
                continue;
            }            
			// 如果金額剛好，則當前組合為最小的組合
            if(subVal==0){
                if(!done.Contains(subVal)) done.Add(subVal,1);
                minComb=1;                
            }
			// 如果金額還有多出，則繼續下一輪的挑選，下一輪會得出最小的組合結果，或者是失敗的組合結果。
            if(subVal>0){
                int comb = PickCoins(coins,subVal,done);
				// 存在組合結果，與當前輪數的結果比較並且繼續計算其他挑選組合的結果。
                if(comb!=-1){
                    if(!done.Contains(subVal)) done.Add(subVal,comb+1);
                    minComb = Math.Min(minComb,comb+1);                    
                }
				// 不存在組合結果，將當前金額標記為沒有組合的結果。
                if(comb==-1){
                    if(!done.Contains(subVal)) done.Add(subVal,-1);
                }                
            }            
        }
		// 如果這一輪所有的條件都沒有達成，則本輪的金額為沒有組合的結果。
        if(minComb==Int32.MaxValue) return -1;
		// 回傳有組合的結果        
        return minComb;
    }
}

複雜度分析：

  • 時間複雜度：最差的結果會是[coins.Length^(amount/最小的硬幣面額)]，所以時間複雜度為O(m^n)。
  • 空間複雜度：Call Stack最差的情況約會是[amount/最小的硬幣面額]，而將結果記錄下來最差的情況會是紀錄所有的組合，約等於[0, 目標金額]的數量，因此空間複雜讀為O(n)，n為amount。

Dynamic Programming

動態規劃的方法利用製作表格的方式來由下往上計算結果。

舉例來說：

  • coins = [1,2,5]
  • amount = 11

動態規劃表如下：

01234567891011
101234567891011
2011223344556
5011221223323

我們將上面的表拆成以下三張方便理解：

  • coins = [1]
  • amount = 11
01234567891011
101234567891011
  • coins = [1]
  • amount = 11
01234567891011
2001020304050
  • coins = [1]
  • amount = 11
01234567891011
5000001000020

可以看到以硬幣面額1來說，湊成0~11的之間的組合很好理解，2和5也是同理。 但是以2和5的表格來看，是沒有辦法滿足0~11所有金額的組合的。

接下來我們將1和2組合起來看：

  • coins = [1,2]
  • amount = 11

動態規劃表的結果如下：

01234567891011
101234567891011
2001020304050

面額1可以單獨完成任務，但是面額2就必須和面額1組合起來完成任務，因此會變成以下的表格：

01234567891011
101234567891011
2011223344556

可以看到面額2沒有辦法完成的單數透過和面額1組合而完成，同時具備[1,2]組合中的最小組合。

接下來加入面額5的表格

  • coins = [1,2,5]
  • amount = 11
01234567891011
101234567891011
2011223344556
5000001000020

同樣的，由於沒有辦法獨立完成所有的金額的組合，因此需要和1、2進行組合，表格如下。

01234567891011
101234567891011
2011223344556
5011221223323

同理最後加入的面額一樣可以得到最小組合。

如果順序打亂呢？

假設面額並不是按照順序排列，表格如下：

  • coins = [5,1,2]
  • amount = 11
01234567891011
5000001000020
101234567891011
2001020304050

我們依然可以透過由左而右、由上而下傳遞並取最小值來完成組合，表格如下：

01234567891011
5000001000020
1012341234523
2011221223323

找出規律

透過上面幾個表格的變化，我們可以找到一個規律，每個金額的最小組合會等於：

金額最小組合 = 最小值(當前組合, (當前位置-當前面額) + 1個面額組合 )。

讓我們回顧剛加入面額5的組合：

  • coins = [1,2,5]
  • amount = 11
01234567891011
101234567891011
2011223344556
5000001000020

由於面額5無法滿足金額小於5的組合，因此由面額1、2的組合向下遞延：

01234567891011
101234567891011
2011223344556
5011221000020

從金額5開始，面額的最小組合會是：

  • 1 : amount[5] = min(amount[5],amount[5-(coin)5]+1);
  • 2 : amount[6] = min(amount[6],amount[6-(coin)5]+1);
  • 2 : amount[7] = min(amount[7],amount[7-(coin)5]+1);
  • 3 : amount[8] = min(amount[8],amount[8-(coin)5]+1);
  • 3 : amount[9] = min(amount[9],amount[9-(coin)5]+1);
  • 2 : amount[10] = min(amount[10],amount[10-(coin)5]+1);
  • 3 : amount[11] = min(amount[11],amount[11-(coin)5]+1);

亂序的規律也一樣

假設面額並不是按照順序排列，表格如下：

  • coins = [5,1,2]
  • amount = 11
01234567891011
5000001000020
101234567891011
2001020304050

面額1可以從金額1開始組合，直到金額5的位置，金額5的位置首先由排序第一的5向下遞延，因此為1，套用上面找出來的規律。

  • 1 : amount[5] = min(amount[5],amount[5-(coin)1]+1);

會等於

  • 1 : amount[5] = min(1,4+1);

最小組合仍然是1，可以證明規律是正確的。

程式碼如下：

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] amounts = new int[amount+1];
        for(int i=0;i<amounts.Length;i++) amounts[i]=amount+1;
        amounts[0] = 0;
        foreach(int coin in coins){
            for(int i=coin;i<amounts.Length;i++){
                amounts[i]= Math.Min(amounts[i],amounts[i-coin]+1);
            }
        }
        return amounts[amount]>amount? -1 : amounts[amount];
    }
}

複雜度分析：

  • 時間複雜度：時間複雜度為O(m*n)。
  • 空間複雜度：空間複雜度為O(n)。

學習重點

  • Recursion
  • Dynamic Programming
Last Updated:
Contributors: eisen