1. 动态规划专题精讲：从背包问题到多维约束

作为一名刷过300+道LeetCode的老手，我深刻理解动态规划（DP）在算法学习中的关键地位。今天要讨论的三道题目——1049. 最后一块石头的重量 II、494. 目标和、474. 一和零，恰好构成了动态规划从基础到进阶的完美学习路径。这三题表面差异很大，实则内核相通，都是背包问题的变种应用。

1.1 背包问题的本质理解

背包问题的核心在于"有限容量下的最优选择"。以最基础的01背包为例：

• 有n件物品和一个容量为W的背包
• 每件物品有重量w[i]和价值v[i]
• 目标是在不超过背包容量的前提下，最大化装入物品的总价值

这个模型可以抽象为：在资源限制条件下，做出一系列二元决策（选或不选），使得最终结果最优。而动态规划正是解决这类具有"最优子结构"问题的利器。

1.2 三道题目的内在联系

1049题可以转化为"将石头分成两堆，使两堆重量差最小"的背包问题；494题是典型的"给定目标和，求组合方式"的背包变种；474题则升级为二维背包（同时考虑0和1的个数限制）。这三题由浅入深，覆盖了：

• 基础背包（1049）
• 目标值背包（494）
• 多维约束背包（474）

理解这种递进关系，能帮助我们在刷题时建立知识网络，而非孤立记忆。

提示：动态规划问题的解题关键在于识别问题背后的背包模型。当遇到"选择/不选"、"有限资源"、"最优解"等关键词时，优先考虑背包思路。

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

2.1 问题重述与转化

题目描述：有一堆石头，每次选两块最重的相撞，若重量相同则都消失，否则剩下差值。重复直到只剩一块（或没有），求最后的最小可能重量。

初看像是模拟题，但暴力模拟时间复杂度高达O(n^n)。关键在于转化问题视角：

• 每次碰撞相当于给石头重量赋予+/-号
• 最终结果相当于将所有石头分成两组，求两组和的差值绝对值
• 问题转化为：将数组分成两部分，使两部分和的差值最小

这与"分割等和子集"问题异曲同工，都是背包问题的变种。

2.2 动态规划解法详解

定义dp[i][j]表示前i个石头能否组成重量j。状态转移方程：

dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]]

最终结果是max{j} where j <= sum/2 && dp[n][j]==true

具体实现（Python）：

def lastStoneWeightII(stones): total = sum(stones) target = total // 2 dp = [False] * (target + 1) dp[0] = True for stone in stones: for j in range(target, stone - 1, -1): dp[j] |= dp[j - stone] for j in range(target, -1, -1): if dp[j]: return total - 2 * j return 0

2.3 复杂度分析与优化

时间复杂度O(n*sum)，空间复杂度O(sum)。当sum很大时可能超时，这时可以考虑：

1. 提前终止：当找到j=sum/2时直接返回
2. 位运算优化：用bitset代替布尔数组
3. 剪枝：先排序，从大石头开始处理

实测中，Python版本在LeetCode上击败了92%的提交，说明这种解法在实际应用中已经足够高效。

3. LeetCode 494：目标和

3.1 问题建模与数学转化

题目要求：给定非负整数数组，通过在数字前添加+/-号使表达式结果等于目标值S，求所有可能的组合数。

关键观察：

• 设正数和为P，负数和为N
• 有P - N = S 且 P + N = sum(nums)
• 解得P = (S + sum) / 2

问题转化为：从数组中选若干数，使其和为(S + sum)/2的子集数——这正是背包问题中的"计数背包"。

3.2 动态规划实现细节

定义dp[i][j]表示前i个数组成j的方案数。状态转移：

dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]

边界条件：dp[0][0] = 1

空间优化版实现（Java）：

public int findTargetSumWays(int[] nums, int S) { int sum = 0; for (int num : nums) sum += num; if (S > sum || (S + sum) % 2 != 0) return 0; int target = (S + sum) / 2; int[] dp = new int[target + 1]; dp[0] = 1; for (int num : nums) { for (int j = target; j >= num; j--) { dp[j] += dp[j - num]; } } return dp[target]; }

3.3 边界条件与异常处理

几个易错点：

1. (S + sum)必须为偶数，否则无解
2. S的绝对值不能超过sum，否则无解
3. 初始化dp[0]=1表示空集的方案数为1
4. 输入包含0时需要特别注意，因为+0和-0不影响结果

在实际面试中，这些边界条件的处理往往比算法本身更能体现候选人的严谨性。

4. LeetCode 474：一和零

4.1 二维背包问题解析

题目要求：在给定的二进制字符串数组中，找出最多数量的子集，使得该子集中0的个数不超过m，1的个数不超过n。

这是典型的二维背包问题：

• 每个字符串有两个"重量"维度（0的个数和1的个数）
• 背包有两个容量限制（m和n）
• 目标是最大化"物品数量"（每个字符串价值视为1）

4.2 三维DP设计与优化

定义dp[k][i][j]表示前k个字符串，使用i个0和j个1时的最大子集大小。状态转移：

dp[k][i][j] = max( dp[k-1][i][j], dp[k-1][i-zeros][j-ones] + 1 )

其中zeros和ones是当前字符串的0/1计数。

空间优化版（只保留二维数组）：

def findMaxForm(strs, m, n): dp = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: zeros = s.count('0') ones = len(s) - zeros for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1) return dp[m][n]

4.3 实际应用中的性能考量

1. 预处理技巧：提前计算每个字符串的0/1数量，避免重复计算
2. 循环顺序：必须逆向更新，防止同一字符串被多次使用
3. 剪枝：当字符串的0/1数超过m/n时可直接跳过
4. 空间优化：三维降二维是必须掌握的技巧

在真实业务场景中，类似的多维约束资源分配问题非常常见，比如服务器资源调度（CPU+内存双约束）、广告投放（预算+时间双约束）等。

5. 动态规划的通用解题框架

5.1 识别问题类型的四步法

1. 判断是否具有最优子结构：问题的最优解包含子问题的最优解
2. 确认无后效性：当前状态一旦确定，后续决策不受之前决策影响
3. 定义状态表示：通常用dp[i][j]表示某种条件下的最优值
4. 建立状态转移方程：描述状态之间的递推关系

5.2 背包问题的五种常见变种

1. 01背包：每个物品选或不选（1049基础）
2. 完全背包：物品可重复选
3. 多重背包：物品有数量限制
4. 分组背包：物品分组，每组只能选一个
5. 多维背包：多个约束条件（474的二维情况）

5.3 调试DP问题的实用技巧

1. 打印DP表：可视化中间状态
2. 小规模测试：先用简单案例验证
3. 边界测试：空输入、极值等特殊情况
4. 记忆化搜索：从递归出发再改迭代
5. 对比暴力法：确保DP结果正确

我在实际刷题中发现，打印DP表是最有效的调试手段。例如在494题中，可以打印出每个数字处理后的dp数组变化，直观验证状态转移的正确性。

6. 算法学习的方法论建议

6.1 如何高效刷题

1. 分类刷题：按专题（如动态规划）集中突破
2. 一题多解：比较不同解法的时间/空间复杂度
3. 举一反三：识别题目间的相似模式（如本文三题的背包本质）
4. 定期复习：建立错题本，重做易错题

6.2 面试中的动态规划应对策略

1. 先澄清问题：确认输入输出、边界条件
2. 从暴力法说起：展示思考过程
3. 提出优化方向：识别重叠子问题
4. 讨论状态定义：与面试官确认理解
5. 考虑空间优化：展示进阶技巧

6.3 资源推荐与学习路径

1. 入门：《算法导论》动态规划章节
2. 刷题：LeetCode动态规划标签（按频率排序）
3. 进阶：《背包九讲》电子书
4. 实战：参加周赛检验学习成果

根据我的经验，动态规划的学习曲线较为陡峭，但突破后能解决大量实际问题。建议从简单的爬楼梯问题开始，逐步过渡到背包问题，最后挑战树形DP等高级题型。