1. 动态规划专题精讲从背包问题到多维约束作为一名参加过多次算法竞赛的老手我深知动态规划DP是许多初学者的噩梦。今天要讨论的这三道LeetCode题目1049、494、474恰好构成了一个完美的动态规划进阶路线从经典的背包问题变种到具有多维约束的复杂场景。这些题目都来自代码随想录算法训练营第35天的内容也是面试中的高频考点。先说说为什么选择这三道题作为组合训练。1049题最后一块石头的重量II本质上是01背包问题的变种494题目标和引入了正负号组合的新维度而474题一和零则升级为二维约束的背包问题。这种编排方式体现了算法训练的经典思路——由浅入深从单一约束到多维约束。关键认知动态规划不是死记硬背模板而是培养将实际问题转化为状态转移方程的能力。这三道题就是训练这种思维的绝佳材料。在工业界应用中类似的动态规划思想随处可见。比如在资源分配、投资组合优化、库存管理等领域都需要处理类似的约束条件下的最优解问题。这也是为什么大厂面试特别青睐这类题目——它们能真实反映候选人解决实际工程问题的能力。2. 1049. 最后一块石头的重量II背包问题的伪装者2.1 问题重述与本质分析题目描述有一堆石头用整数数组stones表示其中stones[i]表示第i块石头的重量。每次选出两块石头进行粉碎假设石头重量分别为x和y如果x y两块石头都会被完全粉碎如果x ! y较轻的石头被粉碎较重的石头重量变为y-x 最终最多只会剩下一块石头返回其最小可能重量。初看这道题很多人会陷入模拟粉碎过程的思维陷阱。实际上这道题的动态规划解法需要转换视角——将问题转化为如何将石头分成两堆使两堆的重量差最小。这与经典的01背包问题如出一辙。2.2 动态规划解法详解解题步骤如下计算所有石头的总重量sum目标转化为找到不超过sum/2的最大子集和使用01背包的动态规划方法求解具体实现Python版本def lastStoneWeightII(stones): total sum(stones) max_weight total // 2 dp [0] * (max_weight 1) for stone in stones: for j in range(max_weight, stone - 1, -1): dp[j] max(dp[j], dp[j - stone] stone) return total - 2 * dp[max_weight]这个解法的时间复杂度是O(n×sum)空间复杂度是O(sum)其中n是石头的数量。2.3 实际编码中的注意事项背包容量上限设置为sum//2而非sum这是优化的关键内层循环需要倒序遍历这是01背包问题的经典写法防止重复计算最终结果是total - 2*dp[max_weight]这个公式体现了两堆重量差的核心思想踩坑提醒在面试中很多候选人能写出背包问题的框架但会忽略最终结果的这个转换公式导致前功尽弃。3. 494. 目标和符号组合的艺术3.1 问题描述与数学建模题目给定一个非负整数数组nums和一个整数target向数组中的每个整数前添加或-然后串联所有整数构成表达式求有多少种组合能使表达式结果等于target。例如nums [1,1,1,1,1], target 3输出5。这道题可以转化为数学问题 设添加的数字和为pos添加-的数字和为neg则有 pos - neg target pos neg sum(nums) 解这个方程组可得pos (target sum(nums)) / 2因此问题转化为在nums中选取若干数使其和等于(target sum(nums))/2有多少种选法。3.2 动态规划状态设计这是一个典型的背包组合问题dp[j]表示填满容量为j的背包有多少种方法。状态转移方程为 dp[j] dp[j - nums[i]]实现代码def findTargetSumWays(nums, target): total sum(nums) if (target total) % 2 ! 0 or abs(target) total: return 0 pos (target total) // 2 dp [0] * (pos 1) dp[0] 1 for num in nums: for j in range(pos, num - 1, -1): dp[j] dp[j - num] return dp[pos]3.3 边界条件与特殊处理需要检查(target sum(nums))是否能被2整除target的绝对值不能超过sum(nums)dp[0]初始化为1表示和为0有一种方法什么都不选实战技巧在面试中应该主动讨论这些边界条件这能展现你思维的全面性。很多候选人只关注核心算法而忽略边界检查这是大忌。4. 474. 一和零二维背包的挑战4.1 问题升级多维约束引入题目给出一个二进制字符串数组strs和两个整数m和n要求找到strs的最大子集大小使得该子集中最多有m个0和n个1。例如 输入strs [10,0001,111001,1,0], m 5, n 3 输出4 解释子集{10,0001,1,0}包含5个0和3个1其他满足条件的子集不更大。这道题将背包问题的维度从一维扩展到了二维需要考虑0和1两个维度的约束。4.2 三维动态规划解法定义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的个数。优化后的二维DP实现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计数避免重复计算性能提示在Python中str.count()比手动遍历字符串计数更快这是语言特性的巧妙利用。5. 动态规划解题的通用方法论5.1 识别问题类型的技巧最优化问题最大值/最小值组合计数问题多少种方式能否将问题分解为重叠子问题是否存在最优子结构5.2 状态设计的思维框架明确状态变量通常包括考虑的范围前i个元素和约束条件如背包容量确定状态表示dp数组的含义建立状态转移方程如何从已知状态推导新状态初始化边界条件确定计算顺序5.3 调试动态规划代码的实用技巧打印DP表格直观检查状态转移是否正确从小规模测试用例开始验证特别注意循环的起始和终止条件检查空间优化后的遍历顺序是否正确在解决这三道题目后我对动态规划有了更深刻的理解它不仅仅是一种算法更是一种将复杂问题分解为可管理子问题的思维方式。这种能力在解决实际工程问题时同样宝贵——无论是系统设计中的资源分配还是业务逻辑中的决策优化都能看到动态规划思想的影子。最后分享一个我在面试中常被问到的变种问题如果474题中的字符串不仅包含0和1而是包含a-z所有字母要求每个字母不超过一定数量该如何扩展解法这留给读者作为思考题核心思路是将二维DP扩展到多维但需要考虑空间复杂度的优化策略。