1049. 最后一塊石頭的重量 II

分成兩堆石頭，一堆石頭的總重量是dp[target]，另一堆就是sum - dp[target]。

在計算target的時候，target = sum / 2 因為是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石頭重量就是 (sum - dp[target]) - dp[target]

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:target = sum(stones) // 2dp = [0 for _ in range(target + 1)]for i in range(len(stones)):for j in range(target, stones[i]-1, -1):dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])return sum(stones) - dp[-1] - dp[-1]

494. 目標和

本題要如何使表達式結果為target，既然為target，那么就一定有 left組合 - right組合 = target。

left + right = sum，而sum是固定的。right = sum - left公式來了， left - (sum - left) = target 推導出 left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出來。此時問題就是在集合nums中找出和為left的組合。

在求裝滿背包有幾種方法的情況下，遞推公式一般為：

dp[j] += dp[j - nums[i]];

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:#dp[j] 表示：填滿j（包括j）這么大容積的包，有dp[j]種方法total_sum = sum(nums)  # 計算nums的總和if abs(target) > total_sum:return 0  # 此時沒有方案#dp[j]:sum_target = j時有多少種不同的組合sum_target = (sum(nums) + target) // 2if (sum(nums) + target) %2 != 0:return 0dp = [0 for _ in range(sum_target+1)]dp[0] = 1 #sum_target為0時只有1中組合法，就是0for i in range(len(nums)):for j in range(sum_target, nums[i]-1, -1):dp[j] += dp[j-nums[i]]return dp[-1]

474. 一和零

這個背包有兩個維度，一個是m 一個是n，而不同長度的字符串就是不同大小的待裝物品。

1. 確定dp數組（dp table）以及下標的含義

dp[i][j]：最多有i個0和j個1的strs的最大子集的大小為dp[i][j]。

此題關鍵：背包是二維的！！但是先遍歷物品再遍歷背包的思想不變！

 class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]#遍歷物品：zeroNum = 0oneNum = 0for s in strs:zeroNum = s.count('0')oneNum = s.count('1')#遍歷背包（需要從后往前）for i in range(m, zeroNum - 1, -1):for j in range(n, oneNum - 1, -1):dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1)return dp[m][n]