昨天，我初步掌握了 0/1 背包问题的理论基础和标准解法。今天，我将这种思想应用到了更广泛的场景中。今天的几道题，乍一看和背包没什么关系，但通过巧妙的数学转化，它们的核心都变成了 0/1 背包问题。

这让我深刻体会到，学习算法不仅仅是学习模板，更重要的是学习一种建模能力——将一个看似全新的问题，转化为我们熟悉的模型来求解。为了加深理解，我对每个适用的问题都同时实现了二维和一维的解法，以观察它们之间的联系和区别。

一、实战演练：识别伪装的背包问题

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

题目描述: 有一堆石头，用整数数组 stones 表示。其中 stones[i] 是第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎…最后，最多只会剩下一块石头。返回此石头最小的可能重量。

• 学习感悟: 这个问题等价于将所有石头分成两堆 A 和 B，并让它们的重量差 |sum(A) - sum(B)| 最小。为了实现这一点，我们需要让其中一堆的重量 sum(A) 尽可能地接近总重量的一半。这完美地转化为了一个 0/1 背包问题：

  • 背包容量: target = total_sum // 2
  • 物品: stones 数组中的每一个 stone
  • 物品重量/价值: stone 的重量
  • 目标: 在容量为 target 的背包里，能装下的最大重量是多少？
    

• 资源包:
  * 题目/文章: https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
  * 视频讲解: https://www.bilibili.com/video/BV14M411C7oV

我的实现 1：二维 DP

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total_sum = sum(stones)target = total_sum // 2n = len(stones)# dp[i][j]: 从0..i-1号石头中任选，放入容量j的背包，能达到的最大重量dp = [[0] * (target + 1) for _ in range(n + 1)]for i in range(1, n + 1):stone_weight = stones[i - 1]for j in range(target + 1):if j < stone_weight:dp[i][j] = dp[i - 1][j] # 装不下，不装else:# 装或者不装dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stone_weight] + stone_weight)sum_A = dp[n][target]sum_B = total_sum - sum_Areturn sum_B - sum_A

我的实现 2：一维 DP (空间优化)

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total_sum = sum(stones)target = total_sum // 2# dp[j]：容量为j的背包，能装下的最大重量dp = [0] * (target + 1)for stone_weight in stones:# 倒序遍历，保证每个石头只用一次for j in range(target, stone_weight - 1, -1):dp[j] = max(dp[j], stone_weight + dp[j - stone_weight])sum_A = dp[target]sum_B = total_sum - sum_Areturn sum_B - sum_A

2. LeetCode 494. 目标和

题目描述: 给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-'。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

• 学习感悟: 这道题是计数型 DP，但同样可以转化为背包问题。假设加 + 的子集和为 P，加 - 的子集和为 N。我们有 P - N = target 和 P + N = total_sum。两式相加得 2P = target + total_sum，即 P = (target + total_sum) / 2。
  • 背包模型: 问题变成了：从 nums 中挑选出一些数，使其和恰好为 new_target = (target + total_sum) / 2，共有多少种挑法？
  • DP 定义: dp[j] 表示和为 j 的组合有多少种。
• 资源包:
  • 题目/文章: https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
  • 视频讲解: https://www.bilibili.com/video/BV1o8411j73x

我的实现 1：二维 DP

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if abs(target) > total_sum or (total_sum + target) % 2 != 0:return 0new_target = (total_sum + target) // 2n = len(nums)# dp[i][j]: 从0..i-1号数中任选，和为j的组合数dp = [[0] * (new_target + 1) for _ in range(n + 1)]dp[0][0] = 1 # 用0个数凑成和为0，有一种方法（什么都不选）for i in range(1, n + 1):num = nums[i - 1]for j in range(new_target + 1):if j < num:dp[i][j] = dp[i - 1][j] # 不选numelse:# 组合数 = (不选num的方法数) + (选num的方法数)dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]return dp[n][new_target]

我的实现 2：一维 DP (空间优化)

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if abs(target) > total_sum or (total_sum + target) % 2 != 0:return 0new_target = (total_sum + target) // 2# dp[j]：和为 j 的组合有多少种dp = [0] * (new_target + 1)dp[0] = 1for num in nums:# 倒序遍历，保证每个数只用一次for j in range(new_target, num - 1, -1):dp[j] += dp[j - num]return dp[new_target]

3. LeetCode 474. 一和零

题目描述: 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

• 学习感悟: 这道题是二维费用的 0/1 背包，是背包问题的一个重要变种。

  • 背包容量: 是一个二维的 (m, n)，分别代表 0 和 1 的容量。
  • 物品: strs 数组中的每个字符串。
  • 物品重量: 每个字符串的重量也是二维的 (count_zeros, count_ones)。
  • 物品价值: 每个字符串价值都是 1。

• DP 定义: dp[i][j] 表示用 i 个 0 和 j 个 1 能构成的最大子集长度。

• 状态转移: dp[i][j] = max(dp[i][j], 1 + dp[i - count_zeros][j - count_ones])。

• 遍历顺序: 因为是 0/1 背包，两个表示容量的循环 i 和 j 都必须倒序遍历。

• 资源包:

  • 题目/文章: https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
  • 视频讲解: https://www.bilibili.com/video/BV1rW4y1x7ZQ

我的实现：二维费用背包

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:# dp[i][j]：用 i 个 0 和 j 个 1 能构成的最大子集长度dp = [[0] * (n + 1) for _ in range(m + 1)]for s in strs: # 遍历物品count_zeros = s.count('0')count_ones = s.count('1')# 倒序遍历背包的两个维度容量for i in range(m, count_zeros - 1, -1):for j in range(n, count_ones - 1, -1):dp[i][j] = max(dp[i][j], 1 + dp[i - count_zeros][j - count_ones])return dp[m][n]

总结

今天我更深刻地理解了 0/1 背包问题的泛用性。它不仅仅是一个求最大价值的模型，通过改变 dp 数组的定义（求最大重量、求组合数、求可行性）和状态转移的方式，它可以解决各种各样的问题。识别问题背后的背包模型，并正确地进行转化，是解决这类 DP 问题的关键所在。从一维费用到二维费用，背包问题的世界真是广阔。