【代码随想录】【动态规划】day43：● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

本文主要是介绍【代码随想录】【动态规划】day43：● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最后一块石头的重量

与分割等和子集类似
在这里插入图片描述

思路：尽量分割成两个sum值相近的数组1和2，求其中一个数组为sum(stone)//2时的一种情况

dp[j]:容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]

def lastStoneWeightII(self, stones: List[int]) -> int:dp = [0] * 15001total_sum = sum(stones)target = total_sum // 2for stone in stones:  # 遍历物品for j in range(target, stone - 1, -1):  # 遍历背包dp[j] = max(dp[j], dp[j - stone] + stone)return total_sum - dp[target] - dp[target]

目标和

思路：分为全为+号和全为-号的两个数组，add+reduce=target add-reduce=sum(nums)
所以add=(sum(nums)+target)/2

dp[j]:填满j（包括j）这么大容积的包，有dp[j]种方法

 def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)  # 计算nums的总和if abs(target) > total_sum:return 0  # 此时没有方案if (target + total_sum) % 2 == 1:return 0  # 此时没有方案target_sum = (target + total_sum) // 2  # 目标和dp = [0] * (target_sum + 1)  # 创建动态规划数组，初始化为0dp[0] = 1  # 当目标和为0时，只有一种方案，即什么都不选for num in nums:for j in range(target_sum, num - 1, -1):dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量return dp[target_sum]  # 返回达到目标和的方案数

一和零

思路：这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。 dp[i][j]
就可以是 dp[i - zeroNum][j - oneNum] + 1。然后在遍历的过程中，取dp[i][j]的最大值。

def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组，初始化为0for s in strs:  # 遍历物品zeroNum = s.count('0')  # 统计0的个数oneNum = len(s) - zeroNum  # 统计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]