代码随想录算法训练营-动态规划-3-(0-1背包问题）|416. 分割等和子集、1049. 最后一块石头的重量 II

416. 分割等和子集

　　01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

　　如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

 1 class Solution:
 2     def canPartition(self, nums: List[int]) -> bool:
 3         _sum = 0
 4 
 5         # dp[i]中的i表示背包内总和
 6         # 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
 7         # 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
 8         dp = [0] * 10001
 9         for num in nums:
10             _sum += num
11         # 也可以使用内置函数一步求和
12         # _sum = sum(nums)
13         if _sum % 2 == 1:
14             return False
15         target = _sum // 2
16 
17         # 开始 0-1背包
18         for num in nums:
19             for j in range(target, num - 1, -1):  # 每一个元素一定是不可重复放入，所以从大到小遍历
20                 dp[j] = max(dp[j], dp[j - num] + num)
21 
22         # 集合中的元素正好可以凑成总和target
23         if dp[target] == target:
24             return True
25         return False

1049. 最后一块石头的重量 II

　　本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。