代码随想录算法训练营 Day 31
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 1049
将问题转化为0-1背包，问题描述就是要将石头分成两堆，并且两堆的重量尽可能接近。因此设置一个背包的容量为总和的一半，尽可能填满这个背包
前四步：
- 使用一维dp数组，dp[i]代表背包容量为i时，背包内可放入的最大重量。本题中石头重量同时代表物品重量和价值
- 递推公式：1. 物品的重量大于背包容量时，那么此时物品肯定无法被放入背包之中，因此dp[i]不会被更新；2. 物品的重量不大于背包容量，那么此时又有两种选择：1）不放入物品，此时dp[i]不更新；2）放入物品i，此时dp[i] = dp[i - weight] + value，放入物品并且在减去该物品重量之后的背包检查是否能放入之前的物品。本题中weight和value都是stones[i]
- 初始化：背包重量为0，无论什么物品都无法放入，因此dp[0] = 0. 后续都会进一步更新，因此也初始化为0
- 遍历顺序：采用一维数组，物品遍历从前往后，背包遍历从后往前
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
s = sum(stones)
target = s // 2
dp = [0] * (target + 1)
for stone in stones:
for j in range(target, -1, -1):
if stone <= j:
dp[j] = max(dp[j], dp[j - stone] + stone)
# target是向下取整，因此另一堆石头的重量为s - dp[-1], 且一定不小于这堆重量
return s - 2 * dp[-1]
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m$) m代表石头总重量的一半，n代表石头数量
Q2. LeetCode 494
与上一题类似，考虑将原数组划分为两堆$s_1$和$s_2$。因为$s_1 + s_2 = sum, s_1 - s_2 = target$，所以$s_1 = (sum + target) / 2$
注意特殊情况：
- 必须得保证能够刚好填满这个背包，因此如果$(sum + target) \% 2 = 1$，说明没有组合方式
- 可能出现$s_1$为负数的情况，即目标值的绝对值大于了总和，所以全加负号也不行，此时也没有组合方式
前四步：
- 使用一维dp数组，dp[i]代表刚好填满容量为j的背包有多少方法
- 递推公式：1. 不能放入背包，dp[i]不会更新；2. 能放入背包，剩余空间还有dp[i - nums[i]]种放入方法，因此dp[i] = dp[i] + dp[i - weight]本题中不涉及取最大值，因为我们是要找到所有可能的方法。数组中数值就是weight
- 初始化：将整个dp数组初始化为0，$dp[0] = 1$背包容量为0时有一种放法，什么都不放
- 遍历顺序：物品从前往后，背包从后往前
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (target + s) % 2 == 1:
return 0
sum1 = (target + s) // 2
if sum1 < 0:
return 0
dp = [0] * (sum1 + 1)
# 本题中数组代表放入方法的数量，而不是价值，因此对于容量为0的背包有1种方法，即什么都不放
dp[0] = 1
for num in nums:
for j in range(sum1, -1, -1):
# 不放入有dp[j]方法，放入有dp[j - num]种方法
if num <= j:
dp[j] = dp[j] + dp[j - num]
return dp[-1]
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m$) m代表背包容量，n代表数组长度
Q3. LeetCode 474
二维的0-1背包问题
再理解！！！
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
c0 = s.count('0')
c1 = s.count('1')
for i in range(m, c0 - 1, -1):
for j in range(n, c1 - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - c0][j - c1] + 1)
return dp[-1][-1]
复杂度分析
时间复杂度：O($k \times m \times n$) 空间复杂度：O($m \times n$) k代表字符串长度