一魚多吃 用找零錢II的DP模型來解 Combination Sum_Leetcode #39

題目在這裡:

題目會給我們一個輸入陣列candidates，和一個目標值 target

問我們，從canditdates裡面重複挑選，可以湊出總和為target目標值的組合數有幾種?

測試範例:

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

約束條件:

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

演算法:

除了傳統的DFS+回溯法backtracking去展開搜索空間的方法之外。

其實，還有一個很優美簡潔的演算法，就是之前學過的Coin Change II的找零錢方法總數的演算法。

這一題，其實背後的框架是無窮背包問題 Unbounded Knapsack Problem

填滿重量為W的背包，給予N個不同物品，每個物品無限量供應。

<=> 等價於

總和為target目標值，給予N個不同數字，每個數字可以重複挑選(相當於無限量供應)。

<=> 等價於

總價值為amount的找零問題，給予N個不同零錢(銅板、紙鈔)，每個零錢無限量供應。

如此一來，我們就用到問題化簡的技巧，把Combination Sum映射到已知解法(演算法)的Coin Change II，再由Coin Change II的解推導出原本Combination的解答。

這種演算法化簡的技巧，在演算法理論也稱之為Reduction，

把一個新的問題A，映射到一個已經知道解法(演算法)的問題B，再透過已知問題B的解答反推問題A的答案。

定義狀態:

DP[ n ] = 找開n元的方法數

初始條件 aka 終止條件:

DP[0] = [ [ ] ] = 空集合，零塊錢

狀態轉移關係式 aka 通則

DP[ n ] += [ DP[ n - current_coin ] + [current_coin] ] if n >= current_coin

白話說，就是大的金額n，
可由小金額的找零方法數DP[ n - current_coin ] +當下銅板current_coin去找開

Bottom-up 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:
　　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 ]

複雜度分析

時間複雜度:

每個銅版有可能被選中，可能沒被選中，又可以被重複選擇，比較鬆的上邊界為O( c * 2^c), 其中 c = candidates陣列的長度。

空間複雜度:

當一元銅板存在時，最深深度可達O(target)

當一元銅板不存在時，最深深度可達O( target / min(candidates) )

Top-down DP程式碼:

class Solution:
　def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
　　
		# use python native cache as memoization for DP memoization
　　@cache
　　def dp(amount, cur_coin_idx, bag):
　　　
　　　## Base case
　　　if amount == 0:
　　　　# initial amount is fully changed with those coins in bag
　　　　return [ bag ]
　　　
　　　elif (amount < 0) or (cur_coin_idx < 0) :
　　　　# Impossible to fill negative amount with coins
　　　　# Impossible to fill amount without coins
　　　　return []
　　　
　　　## General cases
　　　cur_coin = candidates[cur_coin_idx]
　　　
　　　# Type_1: Not to change with current coin
　　　not_to_take = dp(amount, cur_coin_idx-1, bag)
　　　
　　　# Type_2: Change with current coin
　　　take = dp(amount-cur_coin, cur_coin_idx, bag+(cur_coin,) ) 
　　　
　　　return not_to_take + take
　　
　　# ------------------------------------------------------------
　　return dp( target, len(candidates)-1, bag=() )

學完這題的同學，強烈建議回去複習之前的Coin Change II，可以發現背後的原理其實是相通的喔。
演算法畢竟也算是理科，理解後融會貫通，以後題目再變化，也有能力去自己推導出合適的演算法，運用化簡的技巧，把它解開來。

Reference:

[1] Coin Change II - Leetcode

[2] Coin Change II 詳解+分析

[3] 用Coin Change II 的DP模型去解 Combination Sum 詳解 + 分析