合縱連橫: 找零錢的DP框架_理解背後的本質

Sabrianna null on Unsplash

最近會試著寫一些統整類的文章，
幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。

找零錢框架

寫成虛擬碼或演算法，找零錢用了幾枚銅板可以這樣表達

# 銅板數目累加​
# n-coin 元 + coin這枚銅板，就可以湊出n元。
dp[ n ] = dp[ n- coin ] + 1

寫成虛擬碼或演算法，找零錢的方法數可以這樣表達

for coin in coins:
	# 方法數累加​
	# n-coin 元 + coin這枚銅板，就可以湊出n元。
	dp[ n ] += dp[ n - coin ]

接下來，我們會用這個上面這兩種結構，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種DP結構，之後的解說會反覆出現)

最精簡找零 Coin Change I (原本這題的專門教學文章在這裡)

對於 Coin Change I 來說，我們要找的是最精簡的找零數目，也就是
用最少的銅板湊出n元，於是我們就用DP找零錢用了幾枚銅板的演算法來解。
就像下面看到的這樣:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        # key: $value
        # value: minimal coin change of $value
        dp = defaultdict(lambda: math.inf)

        # Base case
        # $0 is reached by taking nothing
        dp[0] = 0

        # General case:
        # Try to make change with current coin
        # 請注意看，剛剛介紹的DP演算法框架就出現在這裡!
        for coin in coins:
            for value in range(coin, amount+1):
                dp[value] = min(dp[value], dp[value-coin]+1 )
        
        
        if dp[amount] == math.inf:
            return -1
        
        return dp[amount]

有沒有別的題目用到同樣的結構?

其實有喔，在Perfect Squares 這題就是。

最精簡找零 的衍伸變形 Perfect Squares

這題要求我們計算整數n的最精簡的完全平方數的化簡次數。

我們可以把n視為目標金額(要找開的對象)，所有小於等於n的完全平方數視為題目供應的銅板陣列，

如此一來，這題就被我們化簡到最精簡找零。

於是我們就用DP找零錢用了幾枚銅板的演算法來解。就像下面看到的這樣:

class Solution:
    def numSquares(self, n: int) -> int:
        
        INF = sys.maxsize
        dp = [ INF for _ in range(n+1) ]
        dp[0] = 0
        
        root = 1
        square = root*root
        
        # for each square number 1, 4, 9, 16, 25...
        # 請注意看，剛剛介紹的DP演算法框架就出現在這裡!
        while( square <= n ) :
            
            # update dp value for number from square to n
            for i in range(square, n+1) :
                
                dp[i] = min( dp[i], dp[i-square]+1 )
            
            # go to next square number
            root += 1
            square = root*root
        
        
        return dp[n]

Perfect Squares 和上面那一題 Coin Change I 九成都很像！對吧~

只是改成特殊的銅板(都是完全平方數)而已，其他思考邏輯都相同。

找零錢的方法總數(嚴格一點說，就是數學上的組合數) Coin Change II
(原本這題的專門教學文章在這裡)

對於 Coin Change II 來說，我們要找的是找零錢的方法總數，就是數學上的組合數(與次序無關)。

例如 $5 + $1 和 $1 + $5 會被視為一種而已(因為組合數不考慮順序)
這是實作上的細節，請特別留意。

想清楚題目要問的
究竟是 組合數(不考慮順序)，還是排列數(考慮順序)，這兩者是有區別的。

於是我們就用DP找零錢的方法數的演算法來解。就像下面看到的這樣:

我們每次迭代時，外圈先固定用某一種銅板針對所有金額去找零錢，確保同一種銅板不會再之後的找零錢過程中重複出現。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        # base case:
        # amount 0's method count = 1 (by taking no coins)
        dp = [1] + [ 0 for _ in range(amount)]
        
        # make change with current coin, from small coin to large coin
        # 請注意看，剛剛介紹的DP演算法框架就出現在這裡!
        for cur_coin in coins:
            
            # update change method count from small amount to large amount
            for small_amount in range(cur_coin, amount+1):
                
                # current small amount can make changed with current coin
                dp[small_amount] += dp[small_amount - cur_coin]
                
        return dp[amount]

好，現在我們知道找零錢的組合數了。

那...假如別的題目要求我們列出找零錢的具體方法呢?

其實有，只是被出題者包裝過，用別的樣貌呈現，但本質還是相同的，

這題就是Combination Sum

找零錢的具體方法 Combination Sum

原本Coin Change II是計算有幾個組合數，
現在Combination Sum是改成紀錄組合的狀態，用同樣的手法更新即可。

於是我們就用DP找零錢的方法數的演算法來紀錄組合的狀態。就像下面看到的這樣:

我們每次迭代時，外圈先固定用某一種銅板針對所以金額去找零錢，確保同一種銅板不會再之後的找零錢過程中重複出現。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        dp = defaultdict(list)
        
        ## Base case:
        # $0 is reached by taking nothing
        dp[0] = [ [  ] ]
        
        coins = candidates
        
        ## General cases:
        # 請注意看，剛剛介紹的DP演算法框架就出現在這裡!
        for coin in coins:
            for amount in range(coin, target+1):
                
                # satisfy $amount from ($amount-$coin) + $coin
                for prev_coin_change in dp[ amount - coin ]:
                    dp[amount] += [ prev_coin_change + [coin] ]
        
        return dp[ target ]

Combination Sum 和上面那一題 Coin Change II 九成都很像！對吧~

只是改成紀錄組合的狀態而已，其他思考邏輯都相同。

那有沒有類似找零錢的題目，但是要考慮順序的呢?也就是要求我們計算排列數的?

其實有，只是被出題者包裝過，用別的樣貌呈現，但本質還是相同的，
這題就是Combination Sum IV

找零錢的方法排列數(嚴格說，就是數學上的排列數) Combination Sum IV

對於 Combination Sum IV 來說，
我們可以把target是為目標金額(要找開的對象)，nums視為題目供應的銅板陣列，
如此一來，這題就被我們化簡到找零錢問題。

由從題意和範例可以知道，這題把不同的順序視為不同的兩種。

例如 $5 + $1 和 $1 + $5 會被視為不同的兩種而已(因為排列數要考慮順序)
這是實作上的細節，請特別留意。

想清楚題目要問的
究竟是 組合數(不考慮順序)，還是排列數(考慮順序)，這兩者是有區別的。

於是我們就用DP找零錢的方法數的演算法來解。就像下面看到的這樣:

我們每次迭代時，外圈反而先迭代所有金額，內圈才迭代每一種銅板針對當下的金額去找零錢，允許同一種銅板在之後的找零錢過程中又重複出現。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        
        ## Dictionary
        # key: amount
        # value: method count to make change up to specific amount
        dp = defaultdict(int)

        # $0 is reached by taking nothing, only one way to do so
        dp[0] = 1

        # For each value in range [1, target]
        # 請注意看，剛剛介紹的DP演算法框架就出現在這裡!
        for value in range(1, target+1):

            # Try each possible coin
            for coin in nums:
                
                # Coin is too big, impossible to make change
                if coin > value: continue

                # Make change with smaller coin
                # $value = $(value-coin) + $coin
                dp[value] += dp[value-coin]
        
        # Total method count to make change up to $target
        return dp[target]

Combination Sum IV 和上面那一題 Coin Change II 九成都很像！對吧~

只是改成紀錄排列數(考慮順序)而已，其他思考邏輯都相同。

細微的差異就是我們用銅板放在內層迴圈還是外層迴圈，
來控制同一種銅板在之後可不可以重複出現。

結語

好，今天一口氣介紹了最精華的部分，

通用的Coin Change 找零錢模型的框架，還有相關的衍伸變化題與演算法化簡流程，

希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~