Unbound Knapsack

除了是非題也會遇到多選題。

可以多次拿取的題型就是Unbound背包問題。

背景知識

• 基礎程式語法
• 背包問題

理解問題

一個總數，多種幣值選取，可以有幾種拿法。

每相同選擇問題就是動態規劃拿手的。

思路視覺化

參考NeetCode

程式化

from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1] * (amount+1) # set all maximum
        dp[0] = 0
        
        for a in range(1, amount+1):
            for c in coins:
                if a-c >= 0:
                    dp[a]= min(dp[a], 1+dp[a-c]) # 1:original amount
                    
        return -1 if dp[amount] == amount+1 else dp[amount] # dp[amount] + 1 is default 

print(Solution().coinChange([1,2,5],11))

複雜度分析

TC: O(a*c)
SC: O(amount+1)

39. Combination Sum

使用DFS。

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

思路視覺化

[2,3,6,7], 7
2+2+3 == 7
7 == 7

程式化

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates: return []
        res = []
        candidates.sort()
        def dfs(idx, path, cur): # 開始加總位置, 建構可能解，目前的值
            if cur > target: return # less than target
            if cur == target: # same as target
                res.append(path)
                return
            for i in range(idx, len(candidates)):
                dfs(i, path+[candidates[i]], cur+candidates[i])
        dfs(0, [], 0)
        return res

複雜度分析

TC: O(nˆ2)
SC: O(path)

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)