1. 两道题为什么值得放在一起精刷——先搞清楚它们各自的脾气力扣刷到动态规划专题152.乘积最大子数组和416.分割等和子集这两道题几乎总是前后脚出现。我第一次刷的时候也很疑惑一个求子数组的乘积最大值一个做集合分割看起来八竿子打不着为什么讨论的人总把它们放一块儿等我把这两道题彻底吃透之后才明白这俩简直是动态规划里最典型的两个性格代表一个靠临场设计状态打天下一个靠识别经典模型走天下。把它们对比着刷比单独刷十道同类题都管用。先说152。这题表面上是53.最大子数组和的乘积版很多人第一反应是我不就是把加号改成乘号嘛结果一跑用例就被负数教育了。乘积和加法最大的不同在于符号翻转——一个正数乘以负数变小一个负数乘以负数反而变大。这意味着光靠以i结尾的最大值这一个状态根本覆盖不了所有可能性。你得额外维护一个最小值因为最小值可能被下一个负数乘成最大值。这种为了处理特殊情况主动加状态的设计思路正是DP从入门到进阶的分水岭。再说416。这题难点不在状态转移方程本身而在于你能否认出它是背包问题。分割成两个和相等的子集翻译成数学语言就是能不能从数组里挑一些数让它们的和恰好等于总和的一半。这不就是01背包的恰好装满吗每个数选或者不选每个数只能用一次目标容量是target。一旦完成这个抽象剩下的就是套背包模板的事。可问题是很多人在第一步就卡住了——他们没见过这种形式的背包自然联想不到。所以说152考验的是你在没有现成套路时设计状态的能力416考验的是你在看似无关的问题里识别经典模型的能力。这两个能力恰好是动态规划刷题路上最核心的两块拼图把它们放一起精刷性价比极高。这篇文章我不会只贴代码我会把状态为什么这么定义、遍历顺序为什么这么写、初始化为什么踩坑踩得死去活来全部摊开来聊一遍。适合正在刷力扣热题100、准备面试算法轮或者DP一直处于看得懂题解、自己写不出来状态的朋友。2. 152.乘积最大子数组——负负得正逼出来的双状态设计2.1 为什么维护最大值还不够一个反例讲透先回顾题目给你一个整数数组nums要找出数组中乘积最大的非空连续子数组返回乘积。注意是连续子数组这意味着你不能跳着选子数组必须是一段连续的区间。最直觉的想法模仿最大子数组和的解法维护以当前位置结尾的最大乘积然后全局取最大值。用公式表达就是state[i] max(state[i-1] * nums[i], nums[i])。这行代码对加法求和完全正确但对乘法会翻车。看一个具体例子nums [-2, 3, -4]。按上面的错误公式推i0state -2全局最大值 -2i1state max(-2 * 3, 3) 3全局最大值 3i2state max(3 * -4, -4) -4全局最大值 3。答案变成了3但实际乘积最大子数组是 [-2, 3, -4]乘积是 (-2) * 3 * (-4) 24。为什么错了因为在 i2 这个位置上真正有用的前置状态是 i1 时的最小值 -6即 -2 * 3只不过我们没保存它早把它丢掉了。而 -6 * (-4) 24一举翻身。这和最大子数组和完全不同。求和时前缀越小加上负数越吃亏所以只需要最大值。但求积时前缀越小乘上一个负数反而可能越大。这就是负负得正给状态设计带来的本质冲击——你没法从单一状态里恢复出翻盘所需的信息。2.2 状态定义与转移方程max/min双轨并进的由来既然一个最大值状态覆盖不住所有情况最直接的解决思路就是把可能翻盘的信息也存下来。于是我们同时维护两个状态maxF[i]以 nums[i] 结尾的乘积最大子数组的乘积minF[i]以 nums[i] 结尾的乘积最小子数组的乘积。转移的时候分别考虑三种来源从前一个位置的最大值乘过来、从前一个位置的最小值乘过来、以及从当前位置重新开始因为子数组可以不包含任何前面的元素nums[i] 单独成为一个子数组。maxF[i] max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i]) minF[i] min(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])这里有个细节值得多说一句为什么要跟 nums[i] 本身比较一遍因为乘积子数组要求连续但你没义务必须从 i-1 接过来。如果 nums[i] 是正数而 maxF[i-1] 是负数那从当前元素重新开始显然是更优的选择。这个自成一派的选项代表子数组的起点可以落在任意位置是状态定义以 i 结尾的必然结果。为什么两个状态就够了因为乘积的符号和大小完全由绝对值和正负决定而绝对值最大的正数就是 maxF绝对值最大的负数就是 minF。任何中间值乘上 nums[i]结果都不会超过这两种情况的组合。所以双状态是完备的不需要维护更多。如果你熟悉高等数学里的闭区间连续函数最值会发现这里的思想很像一个区间内的最大值要么来自左端点值要么来自区间内子区间的最值乘上端点的变化。DP的最优子结构在这里体现得非常清晰。2.3 开始写代码前的三个细节初始化、当前值单独比较、滚动压缩2.3.1 初始化不是从0开始很多新手初始化 maxF 和 minF 会用0然后从 i1 开始遍历。这在nums[0]是负数时会出问题。正确做法是让 maxF minF nums[0]遍历从 i1 开始因为以第0个元素结尾的乘积子数组只有一个选择——就是它自己。2.3.2 先取旧值再更新两个状态代码里如果顺序写错会踩一个非常隐蔽的坑。假设你写maxF max(maxF * nums[i], minF * nums[i], nums[i]) minF min(maxF * nums[i], minF * nums[i], nums[i])第二行用到的 maxF 已经是更新后的新值了而不是 i-1 时刻的旧值。这会让状态转移依赖同一层的新状态逻辑上变成这次乘积又乘了一次当前元素结果完全错误。正确写法必须先存旧值prevMax, prevMin maxF, minF maxF max(prevMax * nums[i], prevMin * nums[i], nums[i]) minF min(prevMax * nums[i], prevMin * nums[i], nums[i])或者用多变量同时赋值的语法。这个坑在空间压缩版本里尤其容易犯因为没有了 dp 数组层面的天然隔离新旧值混在一个变量里稍不留神就串了。2.3.3 空间压缩后的最终形态由于 maxF[i] 和 minF[i] 只依赖 i-1 的状态根本不需要开整个数组两个变量加一个全局结果即可。最终代码大概长这样class Solution: def maxProduct(self, nums: List[int]) - int: maxF minF ans nums[0] for i in range(1, len(nums)): prevMax, prevMin maxF, minF maxF max(prevMax * nums[i], prevMin * nums[i], nums[i]) minF min(prevMax * nums[i], prevMin * nums[i], nums[i]) ans max(ans, maxF) return ans你看核心逻辑不超过十行但每一行背后都有讲究。面试的时候能把上面三个细节讲清楚比背代码有用得多。2.4 手动推演一个用例把递推过程摊开看用 nums [2, -5, -2, -4, 3] 走一遍。初始maxF 2minF 2ans 2。i1nums[1] -5prevMax 2prevMin 2maxF max(2 * -5, 2 * -5, -5) -5minF min(2 * -5, 2 * -5, -5) -10ans max(2, -5) 2。i2nums[2] -2prevMax -5prevMin -10maxF max(-5 * -2, -10 * -2, -2) max(10, 20, -2) 20minF min(-5 * -2, -10 * -2, -2) min(10, 20, -2) -2ans max(2, 20) 20。i3nums[3] -4prevMax 20prevMin -2maxF max(20 * -4, -2 * -4, -4) max(-80, 8, -4) 8minF min(20 * -4, -2 * -4, -4) min(-80, 8, -4) -80ans max(20, 8) 20。i4nums[4] 3prevMax 8prevMin -80maxF max(8 * 3, -80 * 3, 3) max(24, -240, 3) 24minF min(8 * 3, -80 * 3, 3) min(24, -240, 3) -240ans max(20, 24) 24。最终答案是24对应子数组 [2, -5, -2, -4]乘积恰好是2 * (-5) * (-2) * (-4) 80等一下重新算一下——2 * -5 -10-10 * -2 2020 * -4 -80不对。那24是哪个子数组[2, -5, -2, -4] 是 -80不是24。实际上 [2, -5, -2, -4, 3] 整体是 -240也不对。那24来自 [-5, -2, -4](-5) * (-2) * (-4) 10 * (-4) -40不对。仔细看 i4 时 maxF 24 来自 prevMax * 3 8 * 3而 prevMax 8 来自 i3 时的 maxFi3 的 maxF 8 来自 minF[i-1] * nums[3]即 -2 * -4 8。所以路径是以 i1 结尾的最小值 -2子数组 [2, -5]不对[2,-5] 是 -10-10 才对。我重新检查 i2 的 minFmin(10, 20, -2) -2这个 -2 来自当前重新开始 nums[2] -2即以 i2 结尾的最小乘积子数组是 [-2]。然后 i3 时 minF[i-1] -2 乘上 -4 得 8对应的子数组是 [-2, -4]乘积8。接着 i4 时 prevMax 8 乘上 3 得 24对应子数组 [-2, -4, 3]而 (-2) * (-4) * 3 24。这才是正确答案。我的第一次手算路径追踪出了问题但算法本身的结果是对的——这恰恰说明了一个关键点你以为最可能产生最优解的子数组未必是真正的答案DP通过状态存储帮你在所有可能性里自动选出了正确路径哪怕这条路径的起点在很早之前中间还经历了符号的反转。讲这个例子我就想强调手推DP用例中途很容易算串因为你脑子里同时维护的临时状态太多容易把老状态和新状态搞混。这也是为什么我推荐初学者在草稿纸上画表格横轴是下标竖轴是maxF/minF每算一格都把prevMax、prevMin先抄下来。这个习惯能消灭一大半计算错误。3. 416.分割等和子集——把选还是不选翻译成背包问题3.1 第一步不是写代码是把题意翻译成数学命题题目描述很简单给你一个只包含正整数的非空数组nums判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。看到两个子集和相等第一反应应该是总和必须是偶数。如果总和是奇数直接返回 false因为整数和的一半不可能是小数。这不算优化算必要条件先过滤掉一大半无效输入。接下来做翻译设数组总和为 sumtarget sum // 2。问题等价于在这个数组里能否找到一些数使它们的和恰好为 target。因为一旦选出来的子集和是 target剩下的数天然也是 target。题目就变成了从 nums 中选若干个数每个数最多选一次能否恰好凑出 target。这就是01背包里的恰好装满判定问题只不过背包容量是 target物品重量是 nums[i]价值不用管因为这里只关心能不能凑出重量。这个翻译是整道题最重要的步骤。我见过太多人卡在这里他们对着题目想怎么递归枚举子集枚举的话规模到 2^20 就爆炸了而背包的DP解法是 O(n * target)远远更优。你能不能在5分钟内把题意抽象成选数凑和决定了这道题对你来说是一道难题还是一道模板题。3.2 二维DP到一维滚动数组为什么容量必须倒序遍历先写最朴素的二维DP。设 dp[i][j] 表示从前 i 个数中选能否凑出和 j。注意这里的 i 和上题一样是前 i 个不是以 i 结尾含义完全不同。转移关系不选 nums[i]dp[i][j] dp[i-1][j]选 nums[i]前提是 j nums[i]此时 dp[i][j] dp[i-1][j - nums[i]]。两个条件满足任意一个dp[i][j] 就是 true。初始化时 dp[0][0] true表示一个数都不选、和为0是可行的dp[0][j]j 0是 false。这个初始化对应背包里什么都没放进去的合法状态。二维的写法理解起来容易但空间是 O(n * target)在 target 大一点时会浪费不少内存。考虑到 dp[i][j] 只依赖 dp[i-1] 这一行可以压缩成一维 dp[j]。问题来了一维的更新顺序应该顺着还是倒着答案是必须倒着。一维转移dp[j] dp[j] || dp[j - nums[i]]。如果你从 j 0 往 j target 顺着遍历假设当前在处理第 i 个数当你更新 dp[j] 时dp[j - nums[i]] 可能已经被这一轮的更新覆盖了。那覆盖后的值相当于已经用第 i 个数再选了一次于是同一个数被用了两遍从01背包退化成完全背包答案就是错的。反过来倒序遍历 j target 到 nums[i]更新 dp[j] 时dp[j - nums[i]] 还没被本轮更新过仍然保存着上一轮前 i-1 个数的结果。这正好保证每个数只能被用一次。原理清楚了一维背包的代码就永远不会记反。我建议你第一次写背包类题目时永远先写二维再压缩成一维别一上来就写一维然后靠背顺序过关。顺序不是你背下来的是你推导出来的。3.3 剪枝与细节总和奇偶、target定位、提前返回写代码之前有几个细节值得统一处理先算 sum如果 sum 是奇数直接 return Falsetarget sum // 2然后初始化 dp [False] * (target 1)dp[0] True外层循环遍历 nums 中的每个数 num内层循环从 target 倒着遍历到 num。注意内层下限不是 0因为 j num 时根本装不下当前物品状态直接继承不用更新每轮更新后可以检查 dp[target]一旦变成 True可以直接提前返回。因为后面的更新不会再把 True 变成 False已经可达的目标在后续不会再丢失。套用模板class Solution: def canPartition(self, nums: List[int]) - bool: total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): if dp[j - num]: dp[j] True if dp[target]: return True return False这里有个可扩展的点dp[j] dp[j] || dp[j-num] 和 if dp[j-num]: dp[j] True 在布尔值语义下是等价的但后者更直观也更省布尔运算。我喜欢用后者读代码时一眼就能看出只要前面的某个可达状态加上当前数能到j那j就可达。还有一个常见优化是先对 nums 从大到小排序然后在外层循环里检查 if num target: return False不过一般输入都是正整数且target是总和一半单个数超过target时可以直接排除排序还能让大的数先占掉背包空间后续小物品的无效更新变少。这个优化在回溯法里是剪枝利器在DP里也能提升一点常数但对复杂度量级没有实质影响不必强求。3.4 一个完整的推导表看dp值如何一步步被填出来用 nums [1, 5, 11, 5] 走一遍sum 22target 11。最终目标是看 dp[11] 能否变为 true。初始dp [True, F, F, F, F, F, F, F, F, F, F, F]下标 0 到 11。处理 num 1倒序遍历 j 11 到 1j11 时 dp[10] 是 Fdp[11] 保持 F一路下来只有 j1 时 dp[0]True于是 dp[1] True。此时 dp 中下标 0、1 为 True。处理 num 5j11查 dp[6]F不变j10查 dp[5]F不变j9查 dp[4]Fj8查 dp[3]Fj7查 dp[2]Fj6查 dp[1]T于是 dp[6] Truej5查 dp[0]T于是 dp[5] True。此时 True 的下标0、1、5、6。处理 num 11j11查 dp[0]T于是 dp[11] True。检查 dp[target]已经是 True提前返回 True。最终答案 true对应子集 [11] 和 [1, 5, 5]。严格说还有别的分割方式比如 [1,5,5] 对 [11]总之两边都是11。看到这里你会发现背包DP的推导过程相当机械每一轮就是把当前数能到达的所有新的和更新出来。这个能凑出来哪些和的布尔数组视角比抽象地背模板接地气得多。面试时如果你能画出这种表再解释为什么倒序基本就能证明你是真懂而不是背的。4. 两题放在一起对照后我总结出的DP识别框架4.1 接龙式DP vs 背包式DP状态含义决定了遍历顺序把152和416放在一张表里对比你能看到两类DP模型的差异非常明显对比维度152.乘积最大子数组416.分割等和子集状态定义以i结尾的乘积最值前i个数能否凑出j状态依赖dp[i] 依赖 dp[i-1]dp[i] 依赖 dp[i-1] 和 dp[i-1][j-num]是否要求连续必须连续无连续要求每个元素的使用次数必须使用、路径连续最多一次、可跳过遍历方向从左到右自然遍历容量维度必须倒序空间压缩两个变量足够一维数组倒序更新我把第一类叫接龙式DP每个状态强制接在上一个状态后面像接龙一样不能断。第i个元素是否被选不完全由你决定只要它在子数组范围内就必须参与运算状态转移是延续的。最大子数组和、乘积最大子数组、最长递增子序列都有这个味道只是LIS的接更自由一些。第二类叫背包式DP每个元素可选可不选选与不选是真正的分支状态转移是汇合的。两者最本质的区别在于接龙式的dp[i]天然只有一条主流来源链最多加一个重新开始分支所以空间压缩后只需要维护上一轮值背包式dp[j]由大量前置状态汇合而来压缩后为了不让同层更新互相污染必须控制更新方向。这个框架能帮你快速判断一道新题属于哪类。看到连续子数组就想到接龙式看到选一些数凑目标就想到背包式。剩下的就是确定状态维度和具体转移。有这一层意识之后你不会再遇到每道新DP题都像看陌生人一样的感觉。4.2 从这两题延伸出去的变体题清单152的经典变体是 918.环形子数组的最大和改自最大子数组和而非乘积但思路继承了拆环正反取最值。如果你掌握了152的双状态法碰上环形乘积最大子数组这类问题也不会慌环形问题可以拆成普通区间最大值和跨越首尾的区间最大值后者等价于总和减去普通区间最小值乘积版再加一层符号处理即可。还有一类更隐蔽的变体152如果问你乘积最小的非空子数组乘积解题代码几乎一模一样只需要把 maxF/minF 的角色对调。这就是双状态模型的泛化能力一个模型解决最大最小两种问法。416的变体就更丰富了494.目标和给每个数前加正负号求和为target的方案数。翻译后就是选一些数作为正号集合同样是选与不选的背包问题只是目标从能否算出变成方案数量状态数组从布尔值变成计数。1049.最后一块石头的重量II一堆石头两两碰撞求最小可能剩余重量。推导后等价于选一些石头使总重量尽量接近sum/2和416几乎同一个模型只是目标从恰好等于target变成尽量接近target。322.零钱兑换是每种硬币无限用的完全背包474.一和零是两个容量维度的二维背包。它们的祖先都是那一套前i个物品背包容量的状态定义。我强烈建议刷完416后趁热把494和1049做掉。你会发现自己只需要改一点点代码就能通过三道题这种一次配置多处复用的感觉比盲目刷二十道新题还爽。5. 力扣热题100刷题节奏里这两题的正确打开方式5.1 刷题顺序上怎么安排最省力如果你是按力扣热题100的顺序刷动态规划板块里这两道题通常不会离太远。但我不建议完全照单全收地线性刷那样很容易在152这种中等偏上的题上卡很久然后挫败感飙升。我的建议是先刷 53.最大子数组和把以i结尾的接龙式DP模板焊死在脑子里再刷 152.乘积最大子数组体会一个状态不够用的时候主动加状态这个关键跃迁去刷 70.爬楼梯、198.打家劫舍这类一维DP进一步巩固状态定义意识第4步进入背包专题先做 416.分割等和子集然后是 494.目标和、1049.最后一块石头的重量II最后回头用 152 和 416 做对比总结形成你自己的DP题型地图。这套顺序的核心逻辑是先用简单题建立状态迁移的直觉再用中等题体会加状态/模型抽象两种进阶策略最后用变体题巩固。如果你已经能独立写出152和416那动态规划的基础关基本算过了后面像编辑距离、戳气球这类更复杂的题至少你已经有能力分析状态依赖而不是看到题解就慌。5.2 面试时怎么讲这两题才加分面试和刷题是两码事。刷题时你只需要说服自己面试时你要说服面试官。我见过很多候选人代码写得对但讲不出为什么结果面试官只能一直追问最后评价是知道解法但缺乏深度。讲这两题的时候有几个加分的叙事节奏152 的建议讲法先讲暴力思路枚举所有子数组O(n^2)说明问题在哪然后讲最大子数组和的解法指出换成乘法后负数带来的符号翻转让单一状态失效举一个反例比如 [-2, 3, -4]让面试官亲眼看错误发生再引出双状态定义强调额外维护最小值是为了兜住负负得正的翻盘路径最后提空间压缩和状态更新顺序的坑展示你的实战经验。416 的建议讲法先做数学翻译偶数总和的半值是目标指出这题的本质是01背包的恰好装满判定画一个小的dp表递推几步展示你真的理解转移逻辑主动解释为什么容量要从大到小遍历——拿同一个数不能用两次做论证提一句如果题目变成求方案数只需要把布尔dp改成计数dp显示你能举一反三。这两道题在面试中出现频率很高尤其是416很多公司喜欢用它来面中等偏上的候选人因为它能区分背模板和理解模型两类人。你如果能主动讲出每个数只能用一次所以倒序布尔dp和计数dp的切换这些细节评价会明显不一样。6. 最后分享一点个人刷题体会——关于推导、画表和复盘刷DP题最痛苦的一段时期我总结是看得懂题解自己动笔就废。后来我发现破局方法不是刷更多题而是改变刷题方式。第一步是逼自己在看题解前先花至少15分钟只做一件事猜状态定义。哪怕猜错也要猜然后带着错误定义去套用例亲眼看着它失败再思考为什么失败。152能教会你的是失败原因往往是信息不足——你丢掉了最小值这个关键信息416能教会你的是状态本身的维度决定了你能不能承载题目的约束——你需要一个容量维度来承载和恰好等于target。你亲自试错一遍之后对正确状态定义的理解深度远超看十遍别人的推导。第二步是画表。二维DP画网格一维DP画滚动序列。每个格子都填True/False或数值填不下去的时候就回头查转移方程。画表特别能暴露初始化和边界条件的错误。比如416的dp[0]True如果不画表你根本感受不到空集凑出0这个初始化到底有多重要。第三步是复盘时用一句话写下这道题的最关键线索。152我的备注是乘积会翻符号所以要同时记录最大和最小416我的备注是等和分割 背包恰好装满target是总和的半值。写上这么一句话过两周回来复习不需要重新看整篇题解瞬间就能唤醒全部记忆。这就是我自己的DP刷题节奏也是我建议你试试的节奏。这两道题的价值不在于你记住了它们的代码而在于它们逼你跨过两道坎一道是一个状态不够时敢不敢添加状态另一道是能不能把新问题识别成经典模型。跨过去之后后面很多DP题在你眼里会突然变得透明起来。刷题不必贪多这种能同时训练两种核心能力的组合题值得你刷三遍第一遍看懂第二遍默写第三遍在一个月后回来独立写出来。能做到第三遍这两道题才算真正进了你的脑子。