堅持按題型打卡&刷&梳理力扣算法題系列，語言為python3，Day5

• 0-1背包【目標和】
  • 有n個物品，第i個物品的體積為w[i], 價值為v[i]。每個物品至多選一個，求體積和不超過capacity時的最大價值和
  • 常見變形
    • 至多裝capacity，求方案數/最大價值和（max）
    • 恰好裝capacity，求方案數/最大/最小價值和（+）
    • 至少裝capacity，求方案數/最小價值和（min）
• 完全背包【零錢兌換】
  • 有 n 種物品，第 i 種物品的體積為w[i], 價值為v[i]。每種物品無限次重復選，求體積和不超過capacity時的最大價值和
  • 🌟與0-1背包回溯的區別：
    • 在選了一個物品之后，i 是不變的，表示可以繼續選第 i 種物品

目標和

• 題目描述
  
• 代碼參考

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:target += sum(nums)if target < 0 or target % 2:return 0target //= 2 # //和等號之間不能留空格n = len(nums)@cachedef dfs(i,c):if i < 0: # 當前的物品取完了return 1 if c==0 else 0 # 判斷結果是否合法if c < nums[i]: # 勿漏！！如果當前剩余容量c小于nums[i], 則直接return 不選return dfs(i-1,c)return dfs(i-1,c) + dfs(i-1,c-nums[i]) # 否則return兩者（不選 選）相加return dfs(n-1,target)

零錢兌換

• 題目描述

• Tips

  • 首先拿到數組長度
  • 然后定義dfs函數
    • 先寫邊界條件，注意判斷合法情況
    • 再判斷c（背包容量）夠不夠減，不夠的話就直接return不選
    • return max/+/min 不選 選

• 代碼參考

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)@cachedef dfs(i,c): #此處dfs返回值代表的是硬幣個數if i < 0:return 0 if c==0 else inf # 當所有種類物品取完的時候，判斷是否合法，inf代表無窮大if c < coins[i]:return dfs(i-1,c)return min(dfs(i-1,c),dfs(i,c-coins[i])+1)ans = dfs(n-1,amount)return ans if ans < inf else -1