代码随想录算法训练营第36天|1049.最后一块石头的重量II、494.目标和、474.一和零

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

题目链接：1049.最后一块石头的重量II
文档讲解： 代码随想录

本题就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解为01背包问题。
（1）确定dp数组和小标的含义
dp[ j ] 表示容量为 j 的背包，最多可装的价值
（2）递推关系式
dp[ j ] = max(dp[ j ], dp[ j - stones[ i ]] + stones[ i ])
（3）初始化
因为重量都不会是负数，所以dp[j]都初始化为0就可以了
（4）遍历顺序
（5）打印数组

class Solution(object):def lastStoneWeightII(self, stones):""":type stones: List[int]:rtype: int"""target = sum(stones) / 2dp = [0] * (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) - 2 * dp[target]

2.494.目标和

题目链接：494.目标和
文档讲解： 代码随想录

这道题的目的是使得数组和为 target，统计方法数。加减可以看作把数组分为两个部分，一个是正数集合，另一个是负数集合，使得正数集合减去负数集合为 target。同时正数集合加上负数集合等于数组元素和。因此可以得到正数集合的容量为（target + sum) / 2，如果该值不为整数，则数组得不到target，方法数为0。
（1）确定数组和下标
dp[ j ]表示装满背包容量为 j 的所有方法
（2）递推关系式
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法
（3）初始化
dp[0] = 1，若该值为0，则递推结果都为0
（4）遍历顺序
和01背包一样
（5）打印数组

class Solution(object):def findTargetSumWays(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""summ = sum(nums)#判断target是否超过summif abs(target) > summ:return 0if (summ + target) % 2 == 1:return 0else:bagweight = (sum(nums) + target) / 2dp = [0] * (bagweight + 1)#初始化dp[0] = 1for num in nums:for j in range(bagweight, num - 1, -1):dp[j] += dp[j - num]return dp[bagweight]

这道题也可以用回溯算法来做，目标和为（target + sum) / 2。

3.474.一和零

题目链接：474.一和零
文档讲解： 代码随想录

这道题是01背包，只不过背包有两个维度，一个是m，一个是n，而不同字符串就是不同大小的待装物品。
（1）确定数组和下标
dp[ i ][ j ]表示最多有 i 个0和 j 个1的最大子集的大小
（2）递推关系式
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）
（3）初始化
初始化为0
（4）遍历顺序
外层遍历物品，内层从后往前遍历背包容量
（5）打印数组

class Solution(object):def findMaxForm(self, strs, m, n):""":type strs: List[str]:type m: int:type n: int:rtype: int"""#dp数组的定义，i和j都是背包维度的，因此新建均要考虑0的情况dp = [[0] * (n + 1) for _ in range(m + 1)]for s in strs:#遍历物品#统计0和1的个数zero = s.count('0')one = s.count('1')for i in range(m, zero - 1, -1):for j in range(n, one - 1, -1):dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)return dp[m][n]