項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [377] Combination Sum IV 個人解法筆記

題目出處

377. Combination Sum IV

難度

medium

個人範例程式碼 – 2022/5/30 一刷,DP 另解

本題是 Combinations 系列的第 5 題,前面的題目可以參考:

第 1 題:不允許重複,給定數字範圍的全部組合,目標是指定組合內固定的數量。
第 2 題:允許重複,順序不同視為相同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是一個結果」
第 3 題:允許有限重複(題目指定上限數量),求全部組合。
第 4 題:不允許重複,給定數字範圍的全部組合,目標是求指定的和。
第 5 題:允許重複,但順序不同視為不同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是兩個結果」。(這題已經可以當作排列的題目了。)

本題也是背包系列問題的第 6 題,建議初學者可以從第一題開始去學:

第 1 題:最基本的背包問題,不重複 size,物品只有一個,計算組合可能性
第 2 題:最基本的背包問題,不重複 size,物品只有一個,計算最大價值
第 3 題:完全背包問題,有重複 size,物品無限數量,計算最大價值
第 4 題:有重複 size,物品無限數量,計算可能組合 ,「(1,2,3) 與 (2,3,1) 視為相同答案」
第 5 題:有重複 size,物品有限數量,計算可能組合 ,「(1,2,3) 與 (2,3,1) 視為相同答案」
第 6 題:有重複 size,物品無限數量,計算可能「排列」 ,也就是說「(1,2,3) 與 (2,3,1) 視為不同答案」
第 7 題:有重複物品,有限制物品數數量上限,問可能組合
第 8 題:有重複物品,有限制物品數數量上限,問最大價值
第 9 題:變化問題,有重複 size,計算機率
第 10 題:變化問題,只是把 size 面額提高

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

        nums.sort()
        dp = [0 for _ in range(target+1)]

        for each_target in range(1, target+1):
            for num in nums:
                if each_target == num:
                    dp[each_target] += 1
                if each_target - num >= 0:
                    dp[each_target] += dp[each_target - num] # add new case (with more this num)

        # 0 1 2 3 4 
        # 0 0 0 0 0 
        # 1: 1
        # 2: 2 (case 1)
        # 3: 3 (case 2) (case 1)
        # 4: (case 3+1) (case 2+2) (case 1+3)

        return dp[-1]

注意:DFS 時間複雜度為 O(num^target),DP 為(target^2)
類似 DP 強項:把 O(2^n) 優化時間為 O(n^2) 的概念。

算法說明

其實這也是背包問題的一種,只是這類的背包問題「拿背包的順序也會影響到結果」,
因此,我們把拿背包時,分成「之前case」+ 「現在新拿的 num」
於是,我們遇到一個新的數量時,
只需要去計算所有的「可新拿的一個 num」搭配「扣除此 num 價值後,所有可能的組合」,即為答案。

範例

以題目的數字為例:

target 為 4,我們宣告一個 dp 從 0 1 2 3 4

  • 當 target = 0,0
  • 當 target = 1,1 存在 num,0+1
  • 當 target = 2,2 存在 num, 0+1, 再加上「多拿一顆 1 + (dp[1] 的所有組合)」
  • 當 target = 3,3 存在 num, 0+1, 再加上「多拿一顆 1 + (dp[2] 的所有組合)」, 再加上「多拿一顆 2 + (dp[1] 的所有組合)」
  • 當 target = 4,0 再加上「多拿一顆 1 + (dp[3] 的所有組合)」, 再加上「多拿一顆 2 + (dp[2] 的所有組合)」,再加上「多拿一顆 3 + (dp[1] 的所有組合)」

input handling

處理沒有 input nums 的情況,return 0

Boundary conditions

用 for 來控制範圍