題目出處
難度
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 來控制範圍