LeetCode Hot 100打卡第12天：动态规划核心题型与状态转移全解析

今天是我 LeetCode Hot 100 打卡的第 12 天前面的日子把数组、链表、哈希表这些基础结构扫了一遍从今天开始正式进入动态规划专题。Hot 100 动态规划这块题量不小平时面试也是高频考点所以我把 day12 定成「DP 入门 核心题型剖析」一次性把状态定义、转移方程、初始化、空间优化这些关键点揉碎讲清楚。动态规划题有一个特点代码往往很短但思考过程很长。很多人卡住不是因为不会写代码而是不知道 dp 数组到底代表什么、转移方程怎么写、边界怎么处理。今天这篇文章我不想只贴答案而是把每道题的推理链路完整还原顺便把我刷题时踩过的坑和排查思路都放进来希望正在打卡 Hot 100 的朋友能少走弯路。1. 打卡计划和动态规划为什么难1.1 Hot 100 第 12 天我今天做了什么Hot 100 是 LeetCode 上最经典的一百道面试高频题覆盖面广、难度阶梯合理非常适合用来做系统训练。我给自己定的打卡节奏是每天 4 到 6 题按专题推进day12 放在「动态规划」这个专题的第一天。今天完成的题目有四道我特意避开了上来就做困难题先从 70、53 这类 easy 到 medium 的题入手。动态规划不是靠背题而是靠建立一套通用的分析框架。Hot 100 里的动态规划题分布在多个子类型比如一维线性 DP、二维矩阵 DP、区间 DP、背包问题、经典字符串 DP第一天就要做到「一题一框架同类能迁移」。另一点是Hot 100 的动态规划题目题面看似各不相同但内部分析套路高度一致暴力递归 - 记忆化搜索 - 递推 DP - 空间优化。这四步是通用的一旦走通大部分题都能解出来。day12 的主线就是反复练习这条路径直到形成肌肉记忆。1.2 动态规划题型的通用分析套路很多教程一上来就丢状态转移方程看起来很高深但对新手不友好。我的做法是先问自己三个问题这个问题的穷举策略是什么也就是怎么枚举所有可能的解。是否能把大问题拆成相互重叠的子问题如果子问题无重叠那是分治不是 DP。子问题的最优解能否推出原问题的最优解满足最优子结构才能用 DP。举个例子爬楼梯这道题暴力的做法是递归枚举每一级台阶的选择先走 1 步还是先走 2 步每一级都产生两个分支时间复杂度是 O(2^n)。但仔细看会发现f(5)会用到f(4)和f(3)f(4)又用到f(3)和f(2)f(3)被重复计算了这就是重叠子问题。此外走到第 n 级的方式数完全由前两级的方式数决定具备最优子结构。于是我们就把递归改写成 dp 表用空间换时间。这套「暴力的思考方式 递推的实现方式」是动态规划的灵魂。我在 day12 中反复用这套流程先写一个暴力递归哪怕是超时的再画树形递归调用图观察哪些状态被重复计算最后把递归改成迭代。2. 动态规划核心细节解析2.1 状态定义从暴力递归到记忆化搜索动态规划的第一步是定义状态也就是 dp 数组的每个下标代表什么。状态定义错了后面全是白搭。以打家劫舍为例题目说一条街上有一排房屋相邻两间不能同时偷求能偷到的最大金额。暴力递归思路是rob(i)表示从第 i 间房开始到结尾能偷到的最大金额然后分两种情况——偷第 i 间那么下一间不能偷继续从第 i2 间开始不偷第 i 间从第 i1 间开始。取两者较大值。定义好递归函数后画一下递归树会发现很多重复计算比如rob(2)会被rob(0)和rob(1)同时用到。这时用一个 memo 数组记录已经算过的状态就变成了记忆化搜索。再进一步我们观察到rob(i)只依赖rob(i1)和rob(i2)所以可以改成从后往前的递推或者更常见的从前往后的 dp 数组dp[i]表示偷到第 i 间房屋时能获得的最高金额。定义不同转移方程也会不同。我习惯用「以当前元素结尾」或「前 i 个元素的最优解」这两种经典状态定义方式。比如最大子数组和dp[i]通常定义为「以 nums[i] 结尾的连续子数组的最大和」这样转移特别自然。而打家劫舍用「前 i 间房屋能偷到的最高金额」更清晰。2.2 转移方程与边界初始化状态定义好了之后转移方程就是「怎么由已知状态推出未知状态」。这一步最考验对问题的理解也是最容易出错的地方。爬楼梯的转移方程很简单dp[i] dp[i - 1] dp[i - 2]含义是要到达第 i 级台阶可以从第 i-1 级走 1 步也可以从第 i-2 级走 2 步所以方法数等于这两个状态的和。但要注意边界dp[0]表示在地面方法数为 1站在原地是一种「空」方法dp[1]是 1。如果不把dp[0]处理好dp[2]就会算错。这里就是初始化的作用。打家劫舍的转移方程dp[i] max(dp[i - 1], dp[i - 2] nums[i])含义偷到当前房屋时要么不偷当前房屋延续上一间房屋时的最大值要么偷当前房屋那么前一个房屋不能偷所以加上第 i-2 间时的最大值。取两者的较大值。边界就是dp[0] nums[0]只有一间房时就偷它dp[1] max(nums[0], nums[1])前两间房不能都偷取更大。初始化还有一种常见写法把 dp 数组的长度设置为 n1多一个哨兵位置用来处理 i-2 越界问题。比如打家劫舍可以设置dp[0]0dp[1]nums[0]然后从 i2 开始遍历到 n转移时用dp[i] max(dp[i-1], dp[i-2] nums[i-1])。这种写法有个好处不用对i1特判统一从 2 开始初始边界更干净。2.3 空间优化思路动态规划的常见痛点之一是空间复杂度。很多时候我们只需要保留最近几个状态不需要完整的 dp 表空间优化因此特别重要。爬楼梯我们只需要dp[i-2]和dp[i-1]所以用两个变量滚动即可。打家劫舍同理dp[i]只依赖dp[i-1]和dp[i-2]用两个变量prev2和prev1滚动更新。最大子数组和更是只用pre和ans两个变量。遇到矩阵类 DP比如二维网格的最大路径和空间优化通常是把dp[m][n]压缩成dp[n]因为计算当前行时只依赖上一行。这种压缩是有代价的如果后续需要回溯路径就不能直接覆盖得保留额外信息。所以不要为了空间优化把代码写得难懂Hot 100 面试时更看重思路清晰先写出二维 dp 再说优化。3. 今日实操题目全解3.1 题目一爬楼梯LeetCode 70题面很简单每次可以爬 1 或 2 个台阶问爬到第 n 阶有多少种不同方法。我的完整推理过程不考虑递归直接想最后一步。要到达第 n 阶最后一步只可能是从第 n-1 阶走 1 级或者从第 n-2 阶走 2 级。所以到达第 n 阶的方法数 到达第 n-1 阶的方法数 到达第 n-2 阶的方法数。这就是递推公式。Python 实现class Solution: def climbStairs(self, n: int) - int: if n 2: return n dp0, dp1 1, 2 # dp0 保存 dp[i-2]dp1 保存 dp[i-1] for i in range(3, n 1): dp0, dp1 dp1, dp0 dp1 return dp1为什么dp0初始为 1dp1初始为 2因为dp[1]1dp[2]2。从i3开始循环每次滚动更新。也可以用记忆化递归但递归深度在 n 较大时可能栈溢出迭代是更稳的写法。这道题还有一种数学解法斐波那契数列通项公式但说实话 90% 的面试场景想让你展示的是 DP 思维不是炫数学公式所以我按 DP 写。3.2 题目二打家劫舍LeetCode 198这道题我在 2.1 已经分析了暴力递归的拆解过程这里给出完整代码。class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[n - 1]空间优化版class Solution: def rob(self, nums: List[int]) - int: prev2 0 # dp[i-2]初始表示不偷任何房 prev1 0 # dp[i-1]初始表示没遍历前最大为0 for num in nums: curr max(prev1, prev2 num) prev2, prev1 prev1, curr return prev1注意这个写法里prev2初始为 0 代表「一间房都不偷」prev1初始也是 0。循环第一轮时curr max(0, 0 nums[0])相当于偷第一间房的收益。第二轮时prev2变成了第一轮之前的prev1也就是 0prev1变成了curr于是curr max(第一间房收益, 0 第二间房收益)完美对应dp[1] max(nums[0], nums[1])。这里我建议新手先把 dp 数组版本写熟再切换到滚动变量版本避免一上来就懵。3.3 题目三最长回文子串LeetCode 5这道题是 Hot 100 动态规划里非常经典的二维 DP 题。题面是找字符串 s 的最长回文子串。回文串的性质是如果首尾字符相同并且去掉首尾后的子串也是回文串那么当前字符串就是回文串。所以定义dp[i][j]表示子串s[i:j1]是否为回文串。状态转移方程dp[i][j] (s[i] s[j]) and dp[i1][j-1]要注意边界条件单个字符i j一定是回文串dp[i][i] True两个相邻字符j i1只要s[i] s[j]就是回文串不需要检查中间子串遍历顺序也有讲究。因为dp[i][j]依赖dp[i1][j-1]也就是左下标增大、右下标减小所以不能简单地从左到右、从上到下遍历二维表。常见的做法是按子串长度从小到大遍历先处理所有长度为 1 和 2 的子串再处理长度为 3、4……这样保证计算长串时短串结果已经就绪。Python 实现class Solution: def longestPalindrome(self, s: str) - str: n len(s) # 处理特殊情况 if n 2: return s dp [[False] * n for _ in range(n)] start, max_len 0, 1 # 长度为1的子串 for i in range(n): dp[i][i] True # 长度为2的子串 for i in range(n - 1): if s[i] s[i 1]: dp[i][i 1] True start, max_len i, 2 # 长度从3到n for length in range(3, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j] and dp[i 1][j - 1]: dp[i][j] True if length max_len: start, max_len i, length return s[start:start max_len]这道题还有中心扩展法时间复杂度同为 O(n^2)但空间是 O(1)。实际面试中两种解法都可以。不过打卡 Hot 100 的初衷是把 DP 框架练熟所以我优先展示了 DP 写法。为了应对面试追问中心扩展法也要会class Solution: def longestPalindrome(self, s: str) - str: def expand_around_center(left: int, right: int) - str: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return s[left 1:right] res for i in range(len(s)): odd expand_around_center(i, i) even expand_around_center(i, i 1) if len(odd) len(res): res odd if len(even) len(res): res even return res3.4 题目四最大子数组和LeetCode 53这题是 Hot 100 里很经典的一维 DP也是公司面试频率最高的题目之一。题面给定整数数组 nums找出一个具有最大和的连续子数组至少包含一个元素返回其最大和。我分析的第一步是定义状态dp[i]表示以nums[i]为结尾的连续子数组的最大和。为什么一定要以nums[i]结尾因为连续子数组必须有终点这样才能和下一个元素拼接。转移方程dp[i] max(nums[i], dp[i-1] nums[i])解释一下到nums[i]时我们有两种选择——把nums[i]接到前面的最优子数组后面或者从nums[i]重新开始一个新的子数组。如果dp[i-1] nums[i]比单独nums[i]还小说明前面的和是负数拖后腿了不如重新开始。代码class Solution: def maxSubArray(self, nums: List[int]) - int: pre 0 ans nums[0] for num in nums: pre max(num, pre num) # 这就是dp[i] ans max(ans, pre) return ans这里pre一直在滚动更新等同于 dp 数组中的当前值。我踩过的坑是把ans初始化为 0导致全负数数组时返回 0。所以初始值必须设为nums[0]或者用float(-inf)。这个细节非常值得注意。4. 实战中遇到的坑与排查方法4.1 数组越界和初始化错误动态规划的题目写多了最常见的报错就是IndexError: list index out of range。我总结主要有三个原因dp 数组长度设置错误——比如打家劫舍n1 时还去访问dp[1]必然越界。解决方法是先做特殊判断if n 1: return nums[0]。循环下标起始位置错误——有的题目状态依赖i-2循环从i0开始就会越界。我习惯先把数组长度、依赖关系写清楚再确定从哪里开始循环。举个例子爬楼梯如果从i0开始dp[i-2]就是负数下标Python 里负数下标会访问列表末尾结果全是错的。DP 表遍历方向错误——尤其二维 DP比如最长回文子串如果没按长度递增方向遍历计算dp[i][j]时dp[i1][j-1]可能还没有被赋值。排查技巧在循环开头打印i、j和当前 dp 表用很小的测试用例n1、n2、n3肉眼走一遍比盯着代码发呆有效十倍。4.2 状态转移漏排和逻辑错误有些题目初看能用 DP但转移方程写得不对导致答案差一点点。比如打家劫舍的变种「打家劫舍 II」房屋围成了一个环。如果你照搬线性版本的转移会发现第一个房屋和最后一个房屋被同时偷了违反规则。解决办法是把问题拆成两条线偷第一间房则排除最后一间偷最后一间则排除第一间分别做一次线性 DP然后取最大值。再比如最大子数组和如果题目改成「输出对应的子数组」那么只记录最大值就不够还要记录子数组的起止下标。理解了状态定义之后这类扩展就自然能想通。我还发现一个高频错误循环里忘了更新答案变量。很多人写了 dp 数组最后直接返回dp[n-1]这在爬楼梯里是对的因为答案是最后一步但在最大子数组和中dp[i]代表的是「以 i 结尾」的值全局最大不一定在最后必须先ans max(ans, dp[i])。同样最长回文子串里如果只更新dp表而不记录最长的start和max_len最后就只能返回整个字符串逻辑错误非常隐蔽。4.3 空间压缩后的细节问题把二维 DP 压缩到一维时判断遍历方向会变得更重要。比如「不同路径」这个问题dp[i][j] dp[i-1][j] dp[i][j-1]。压缩成dp[j] dp[j-1]时dp[j]本质上代表上一行的旧值必须从左到右遍历。如果我们反过来从右到左就会覆盖还没用的上一行数据。压缩遍历方向有几个死记硬背但好用的规则如果转移只依赖上一行和当前行左边的值就从左到右遍历。如果依赖上一行和当前行右边的值就从右到左遍历。如果依赖同一行更早计算的位置只要注意当前行的值已经更新即可。实际上最稳妥的方法是在纸上画出二维表格标出依赖箭头自然就知道遍历方向了。5. Hot 100 动态规划经典题型清单5.1 背包类问题入门Hot 100 里有一类动态规划题跟背包问题有关典型代表是「分割等和子集」LeetCode 416。这题本质是 0-1 背包给定一个数组能否找到一个子集使其和等于总和的一半。我做这道题时先把问题转成是否存在一些元素它们的和恰好等于target sum(nums) / 2。如果总和是奇数直接返回 False。然后定义dp[i][j]表示前 i 个元素是否能凑出和 j。转移方程dp[i][j] dp[i-1][j] or dp[i-1][j - nums[i-1]]意思是当前元素不选或者选了之后把剩余和交给前面的元素凑。这道题很适合用来理解「选择与不选择」这一类 DP和打家劫舍的「偷与不偷」完全同构。我建议 day12 之后的下一次打卡先把 416 这道题做熟再用 0-1 背包的思想去解决一堆变种题。背包类 DP 是 Hot 100 动态规划里覆盖面最大的子类型值得单独花一个半天来集中研究。5.2 区间 DP 与字符串最长回文子串属于区间 DP因为它是在一个区间的左右边界上做状态转移。Hot 100 里类似的还有「编辑距离」LeetCode 72和「正则表达式匹配」LeetCode 10它们本质也是二维 DP只是状态转移稍复杂。编辑距离的状态定义是dp[i][j]表示把 word1 的前 i 个字母转换成 word2 的前 j 个字母所需的最少操作数。转移分为两种情况字符相等时直接继承dp[i-1][j-1]不等时考虑增、删、改三种操作取最小。这类题目的难点在于找清楚三个操作各自对应哪个状态而不是背方程。我在 day12 里先做最长回文子串就是为了把二维 DP 的「定义状态、确定依赖、控制遍历顺序」整条链路跑通后面做编辑距离会轻松很多。5.3 接雨水等经典Hot 100 里的「接雨水」LeetCode 42也是动态规划专题下的常客虽然很多人用双指针做但它的 DP 解法很有意思对每一列计算它能接的雨水量 min(左边最高柱, 右边最高柱) - 当前柱高。用两个数组left_max[i]和right_max[i]预先算出每个位置左右两边的最大高度然后再遍历一次求和。这就是典型的「预处理DP」思想和最长回文子串中的子串真值表有异曲同工之妙。我打卡时给自己定了一个原则不要满足于一种解法。Hot 100 的很多题目能同时用贪心、双指针、滚动数组、记忆化搜索实现但我们必须至少掌握一种 DP 解法因为 DP 是一种「通用思维方式」。遇到新题时即使一时没想到最优解法也能用 dp 框架推导出一个可行解再逐步优化。结语day12 给我的收获说实话之前我对动态规划是有畏难情绪的总觉得要背很多状态转移方程。但今天按「暴力递归 - 记忆化 - 递推 - 滚动变量」的顺序把四道题走下来我发现 DP 的核心不是背而是做决策的取舍。爬楼梯的「最后一步怎么走」、打家劫舍的「偷当前还是不偷」、最大子数组和的「接前面还是重新开一段」全都是一个局部决策把每个局部决策做到最优全局自然最优。最后分享一个我自己的小习惯每做完一道 dp 题我会在草稿纸上手动模拟一遍长度为 4 或 5 的小数据把 dp 数组的每一步变化写出来再和代码逐行对照。这个过程看着笨但非常有效很多隐晦的初始化问题和遍历顺序问题都是在模拟中发现的。Hot 100 的打卡是一个持续的过程day12 只是动态规划的开始后面还有更多变种题在等着。希望这篇记录能陪你一起把 DP 这座山越过去。