化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377

Omid Armin on Unsplash

題目敘述 Combination Sum IV

給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。

請問有多少排列數可以湊出target？

註: 排列數的意思就是位置不同代表兩種不同的方法數。

例如(1,1,2), (1,2,1)是兩種湊出target=4的方法數

測試範例

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7

Explanation:
The possible combination ways are:
總共有七種排列數，可以湊出總和 = target = 4​
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

無解，沒辦法從9湊出總和 = target =3​

觀察 湊出總和=target 相當於日常找零錢的過程

整數陣列nums就相當於銅板(零錢)陣列

target值 就相當於 目標金額

例如 nums=[1,5,10], target=7

原題目等價於問我們:
從1元銅板、5元銅板、10元銅板去 湊出7元的排列方法數有幾種?

找錢的過程中，都可以用更小的金額搭配銅板去找開。

我們可以定義DP[ n ] = n元的找零方法總數。

DP[7]

= DP[7-1] + DP[7-5], 七元可以用1元銅板、5元銅板去找零

= DP[6] + DP[2]

有四種 {1,1,1,1,1,1,1}, {1, 5, 1}, {5, 1, 1}, {1, 1, 5} 排列方法數去湊出7元

所以DP[7] = 4, 有四種排列方法數去湊出7元。

DP[ 目標金額 ] += DP[ 目標金額 - 銅板面額 ] for 每個供應的銅板

DP[ target 元 ] += DP[ target - number ] for number in nums

演算法 化簡到找零錢DP框架

1.定義DP狀態

我們可以定義DP[ n ] = n元的找零方法總數。

最終所求是什麼?

目標是target元的找零錢方法數，更精確地說，是排列方法數。

DP[ target ] 就是最終答案。

2.推導DP狀態轉移關係式

找錢的過程中，都可以用更小的金額搭配銅板去找開。

DP[ 目標金額 ] += DP[ 目標金額 - 銅板面額 ] for 每個供應的銅板

DP[ target 元 ] += DP[ target - number ] for number in nums

寫成虛擬碼，就像這個樣子

for number in nums:
    DP[target] += DP[ target - number ] 

對照一下原本的找零錢，結構其實雷同

for coin in coins:
		DP[target] += DP[ target - coin ]

3.釐清DP初始條件

最小規模的問題是什麼?

當目標金額經過找零錢的步驟不斷化簡之後，目標值target越來越小，最後

target = 0的時候，到達最小規模。

零塊錢 就是什麼都不拿 = 0元，只有唯一一種方法。
DP{ 0 ] = 1

程式碼 化簡到找零錢DP框架

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:

        ## DP table
        # key: target
        # value: method count sum up to target
        dp = {}

        def coinChange(target=0):

            if target < 0:
                # Base case
                return 0

            elif target in dp:                
                # Look-up DP table
                return dp[target]

            elif target == 0:                
                # Base case
                dp[0] = 1
                return 1

            # General cases
            count = 0
            for i in range(0, len(nums)):
                count += coinChange( target - nums[i] )
                
            dp[target] = count
            return count

        # ---------------------
        return coinChange(target=target)

複雜度分析

時間複雜度:O(n * target)

針對每個目標金額0~target，用每一種銅板(更小的數字)去找開，計算找零錢的排列方法數。

空間複雜度: O(target)

DP table 需要紀錄每個目標金額的找零方法數， 所需空間大小為O(target)。

關鍵知識點 化簡到找零錢DP框架

挑選數字去湊出總和=target 相當於日常找零錢的過程

把組合數之和化簡到找零錢的DP框架，用已知的找零錢DP演算法去解題。

強烈建議跟著複習相關的Coin Change II 和 演算法框架統整:
合縱連橫: 找零錢的DP框架_理解背後的本質、
觸類旁通: 用 DFS回溯法框架 解 組合數之和 Combination sum 全系列題。
去鞏固知識點，強化理解與認識、加深印象。

Reference:

[1]Combination Sum IV - LeetCode

回到DP特訓班目錄 和 學習路徑