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最后一块石头的重量 II2.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具体实现Pythondef 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 02.3 复杂度分析与优化时间复杂度O(n*sum)空间复杂度O(sum)。当sum很大时可能超时这时可以考虑提前终止当找到jsum/2时直接返回位运算优化用bitset代替布尔数组剪枝先排序从大石头开始处理实测中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空间优化版实现Javapublic 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 边界条件与异常处理几个易错点(S sum)必须为偶数否则无解S的绝对值不能超过sum否则无解初始化dp[0]1表示空集的方案数为1输入包含0时需要特别注意因为0和-0不影响结果在实际面试中这些边界条件的处理往往比算法本身更能体现候选人的严谨性。4. LeetCode 474一和零4.1 二维背包问题解析题目要求在给定的二进制字符串数组中找出最多数量的子集使得该子集中0的个数不超过m1的个数不超过n。这是典型的二维背包问题每个字符串有两个重量维度0的个数和1的个数背包有两个容量限制m和n目标是最大化物品数量每个字符串价值视为14.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 实际应用中的性能考量预处理技巧提前计算每个字符串的0/1数量避免重复计算循环顺序必须逆向更新防止同一字符串被多次使用剪枝当字符串的0/1数超过m/n时可直接跳过空间优化三维降二维是必须掌握的技巧在真实业务场景中类似的多维约束资源分配问题非常常见比如服务器资源调度CPU内存双约束、广告投放预算时间双约束等。5. 动态规划的通用解题框架5.1 识别问题类型的四步法判断是否具有最优子结构问题的最优解包含子问题的最优解确认无后效性当前状态一旦确定后续决策不受之前决策影响定义状态表示通常用dp[i][j]表示某种条件下的最优值建立状态转移方程描述状态之间的递推关系5.2 背包问题的五种常见变种01背包每个物品选或不选1049基础完全背包物品可重复选多重背包物品有数量限制分组背包物品分组每组只能选一个多维背包多个约束条件474的二维情况5.3 调试DP问题的实用技巧打印DP表可视化中间状态小规模测试先用简单案例验证边界测试空输入、极值等特殊情况记忆化搜索从递归出发再改迭代对比暴力法确保DP结果正确我在实际刷题中发现打印DP表是最有效的调试手段。例如在494题中可以打印出每个数字处理后的dp数组变化直观验证状态转移的正确性。6. 算法学习的方法论建议6.1 如何高效刷题分类刷题按专题如动态规划集中突破一题多解比较不同解法的时间/空间复杂度举一反三识别题目间的相似模式如本文三题的背包本质定期复习建立错题本重做易错题6.2 面试中的动态规划应对策略先澄清问题确认输入输出、边界条件从暴力法说起展示思考过程提出优化方向识别重叠子问题讨论状态定义与面试官确认理解考虑空间优化展示进阶技巧6.3 资源推荐与学习路径入门《算法导论》动态规划章节刷题LeetCode动态规划标签按频率排序进阶《背包九讲》电子书实战参加周赛检验学习成果根据我的经验动态规划的学习曲线较为陡峭但突破后能解决大量实际问题。建议从简单的爬楼梯问题开始逐步过渡到背包问题最后挑战树形DP等高级题型。