今天是我 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 间，那么下一间不能偷，继续从第 i+2 间开始；不偷第 i 间，从第 i+1 间开始。取两者较大值。
定义好递归函数后，画一下递归树会发现很多重复计算，比如rob(2)会被rob(0)和rob(1)同时用到。这时用一个 memo 数组记录已经算过的状态，就变成了记忆化搜索。再进一步，我们观察到rob(i)只依赖rob(i+1)和rob(i+2)，所以可以改成从后往前的递推，或者更常见的从前往后的 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 数组的长度设置为 n+1，多一个哨兵位置，用来处理 i-2 越界问题。比如打家劫舍可以设置dp[0]=0，dp[1]=nums[0]，然后从 i=2 开始遍历到 n，转移时用dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。这种写法有个好处：不用对i=1特判，统一从 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初始为 1，dp1初始为 2？因为dp[1]=1，dp[2]=2。从i=3开始循环，每次滚动更新。
也可以用记忆化递归，但递归深度在 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（也就是 0），prev1变成了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:j+1]是否为回文串。状态转移方程：
dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
要注意边界条件：
- 单个字符
i == j一定是回文串，dp[i][i] = True - 两个相邻字符
j == i+1，只要s[i] == s[j]就是回文串，不需要检查中间子串
遍历顺序也有讲究。因为dp[i][j]依赖dp[i+1][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 数组长度设置错误——比如打家劫舍，n=1 时还去访问
dp[1]，必然越界。解决方法是先做特殊判断，if n == 1: return nums[0]。 - 循环下标起始位置错误——有的题目状态依赖
i-2，循环从i=0开始就会越界。我习惯先把数组长度、依赖关系写清楚，再确定从哪里开始循环。举个例子：爬楼梯如果从i=0开始，dp[i-2]就是负数下标，Python 里负数下标会访问列表末尾，结果全是错的。 - DP 表遍历方向错误——尤其二维 DP，比如最长回文子串，如果没按长度递增方向遍历，计算
dp[i][j]时dp[i+1][j-1]可能还没有被赋值。
排查技巧：在循环开头打印i、j和当前 dp 表，用很小的测试用例（n=1、n=2、n=3）肉眼走一遍，比盯着代码发呆有效十倍。
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 这座山越过去。