給定一個輸入陣列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
整數陣列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[ n ] = n元的找零方法總數。
最終所求是什麼?
目標是target元的找零錢方法數,更精確地說,是排列方法數。
DP[ target ] 就是最終答案。
找錢的過程中,都可以用更小的金額搭配銅板去找開。
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 ]
最小規模的問題是什麼?
當目標金額經過找零錢的步驟不斷化簡之後,目標值target越來越小,最後
target = 0的時候,到達最小規模。
零塊錢 就是什麼都不拿 = 0元,只有唯一一種方法。
DP{ 0 ] = 1
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)
針對每個目標金額0~target,用每一種銅板(更小的數字)去找開,計算找零錢的排列方法數。
DP table 需要紀錄每個目標金額的找零方法數, 所需空間大小為O(target)。
挑選數字去湊出總和=target 相當於日常找零錢的過程
把組合數之和化簡到找零錢的DP框架,用已知的找零錢DP演算法去解題。
強烈建議跟著複習相關的Coin Change II 和 演算法框架統整:
合縱連橫: 找零錢的DP框架_理解背後的本質、
觸類旁通: 用 DFS回溯法框架 解 組合數之和 Combination sum 全系列題。
去鞏固知識點,強化理解與認識、加深印象。
[1]Combination Sum IV - LeetCode