2月12日这天我按计划刷完了LeetCode的70、71、72三道题。说实话这几道题很多刷题攻略都建议分开练但我偏偏把它们排在了一起原因很简单这三题恰好串起了一条从一维DP到栈模拟再到二维DP的能力递进线。一天之内连续啃下来比分散在三天刷的收获要大得多。这篇文章就把当天我自己的做题思路、代码实现、踩坑过程完整记录下来给同样在按题号刷题的朋友做一个参考。先说清楚这三道题分别是什么70. 爬楼梯每次可以爬1阶或2阶问爬到第n阶有多少种不同方法。71. 简化路径给定Unix风格的绝对路径要求简化成规范路径。72. 编辑距离计算把一个单词转换成另一个单词所需的最少操作次数操作包括插入、删除、替换。三道题里有两道是动态规划一道是栈模拟。如果你刚开始学算法或者正在准备面试这三题都是非常典型的训练样本。下面我按当天做题的顺序把每一步思考过程都展开讲。1. 为什么把这三道题放在同一天刷1.1 题目本身是什么先给没刷过这些题的朋友快速解释一下题目背景。爬楼梯的问题实际上问的是“n阶楼梯一次跨1步或2步总共有多少种上楼方式”。这是一个非常经典的动态规划入门题很多教材都会用斐波那契数列来引入。简化路径问题输入类似/a/./b/../../c/这样的字符串要求按照Unix路径规则化简。过程中有两个关键规则.表示当前目录直接忽略..表示返回上一级目录需要弹出当前目录。编辑距离问题要求计算两个字符串之间的最小编辑距离。比如把horse变成ros最少需要三步。这道题是文本相似度、拼写纠错、基因序列比对等领域的基础模型。1.2 三题之间的能力递进关系把这三题放在一起最核心的原因是它们形成了一个能力梯度。第70题只涉及一个状态维度也就是“当前在第几阶”状态转移是线性的适合作为动态规划的“热身运动”。第72题则把状态变成二维同时还需要考虑三个方向的转移来源难度明显上升。而第71题虽然不涉及DP却考察了字符串处理和栈这个数据结构的边界处理能力。这种“一维DP 栈模拟 二维DP”的组合正好覆盖了面试算法题里的几大高频考点。一天之内连续接触三种不同思想记忆会更深刻尤其是第70题和第72题之间的对比能让你直观感受到“从一维到二维”的DP思维变化。1.3 每日刷题量的安排逻辑很多人刷题容易陷入两个极端一是每天只刷一道简单题没有压力也没有提升二是追求题量一天刷十道结果每道都是抄答案。我的经验是每天三到四题是比较合适的量而且这三四题之间最好有内在关联。比如今天安排70、71、72原因就是它们的“解法血缘”有关系第70题和第72题都是DP但状态规模不一样第71题是栈但它和第70题有共同点都涉及“当前位置的前后依赖”只是实现手段不同。这样安排你在刷完第70题后进入第71题的栈世界再带着这种状态去看第72题会更清楚不同数据结构和DP分别适合解决什么问题。2. 第70题爬楼梯——动态规划的热身2.1 题意与切入点题目说得很直白你站在楼梯底部要走到第n阶每一步可以走1阶或2阶问走法总数。我第一次遇到这题时第一反应是递归枚举所有走法于是写了一个climbStairs(n) climbStairs(n-1) climbStairs(n-2)。这个式子本身是对的但直接递归会导致大量重复计算。比如算n10climbStairs(8)会被重复调用很多次。这在LeetCode上会超时。正确的切入点是意识到这个递推关系和斐波那契数列完全一致只不过初始值不同。到第1阶只有1种走法到第2阶有2种走法于是从第3阶开始每一阶的走法数等于前两阶之和。2.2 从递归到记忆化再到迭代很多人会直接背DP写法但我的建议是先把递归思路走一遍再做优化。递归的思路就是从终点往回推要到达第n阶最后一步要么从第n-1阶跨1阶过来要么从第n-2阶跨2阶过来。所以到达第n阶的总方法数就是把到达第n-1阶和第n-2阶的方法数相加。def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这个版本用一个数组存下了每一步的答案时间复杂度O(n)空间复杂度O(n)。如果继续优化会意识到我们每次只用到了前两个状态所以没必要保留整个数组用两个变量滚动更新就行。def climbStairs_optimized(n: int) - int: if n 2: return n prev, cur 1, 2 for _ in range(3, n 1): prev, cur cur, prev cur return cur空间从O(n)降到了O(1)。这种滚动数组的优化思路在后面第72题里还会用上所以刷这题时一定要把“为什么可以只保留前两个值”想透彻。2.3 复杂度分析与变形题这一题的标准时间复杂度是O(n)如果遇到n特别大的场景比如n达到10的18次方还可以用矩阵快速幂把复杂度降到O(logn)或者直接用斐波那契通项公式。面试中一般不要求但提一嘴会让面试官觉得你知识面广。第70题最常见的变形包括一次可以爬1、2、3阶有一个台阶不能踩最少跳几次能到顶。这些变形都有一个共同点就是状态转移关系仍然是根据“最后一步从哪里来”反推。只要掌握这个分析套路变形题都不会太难。提示如果你刷这题时觉得“递推式好简单但还是不知道自己怎么写出来的”建议拿一张纸把n1到n5的走法全部列出来再对照代码看一遍。这个题目虽然简单但它是理解DP“状态定义”和“转移方程”之间关系的最好入门素材。3. 第71题简化路径——用栈处理字符串3.1 题意与边界陷阱第71题是一道看起来很繁琐、但解法非常固定的题。输入是Unix风格绝对路径例如/a/./b/../../c/输出要求是规范化后的路径规则有三条多个连续/只保留一个。.表示当前目录直接忽略。..表示回到上一级目录如果已经在根目录则忽略。这道题的核心不是“会不会栈”而是“能不能把所有边界情况一次性想清楚”。我见过很多人代码写对了但在/../这种输入上翻车还有人在/a//b这种连续斜杠上出错。3.2 栈模拟的完整过程解法用栈非常自然把路径按/切分成若干段遍历每一段根据段内容决定是压栈、弹栈还是跳过。def simplifyPath(path: str) - str: stack [] for part in path.split(/): if part or part .: continue if part ..: if stack: stack.pop() else: stack.append(part) return / /.join(stack)这里的关键细节是path.split(/)。比如输入/a//b按/切分后得到[, a, , b]空字符串会被忽略掉所以连续斜杠不会造成问题。输入/a/./b会得到[, a, ., b].也被忽略。输入/a/../b会得到[, a, .., b]遇到..时把栈里的a弹掉最后只剩b。我实际写的时候发现Python里split真的好用但如果你用C或者Java需要注意split函数的边界行为Java的split会保留前导空字符串C的std::getline处理起来稍麻烦。任何语言核心逻辑都是同一套。3.3 常见错误与边界用例这题的高频错误主要有三个没有处理..在根目录的情况比如/../正确输出是/不是//或者报错。根据规则栈为空时遇到..应该直接忽略。最后拼接路径时忘记加开头的/。比如栈里最后是[a, b]正确结果是/a/b没有开头斜杠是错的。把...当成..处理。注意只有恰好两个点的字符串才是“返回上级目录”...是合法的目录名。我建议刷这题时多跑几个边界用例至少要把/home/、/../、/home//foo/、/a/./b/../../c/、/.../a这五种情况都验证一遍。尤其是最后一个/.../a...要当成普通目录名压栈很多题解没提这个点但这个恰恰是面试官爱挖的坑。4. 第72题编辑距离——二维DP的经典模型4.1 题意与状态定义编辑距离这题我第一次看的时候被“编辑距离”四个字吓到了觉得很高深。实际上它要解决的问题是给定两个字符串word1和word2每次可以对word1做三种操作之一插入一个字符、删除一个字符、替换一个字符问最少需要多少次操作能让word1变成word2。这道题的关键是定义DP状态。我用dp[i][j]表示“把word1的前i个字符转换成word2的前j个字符所需的最少操作次数”。注意这里i和j指的不是字符下标而是长度。比如word1 horseword2 rosdp[3][2]表示把hor变成ro的最少步数。这个状态定义是很多新人最容易卡住的地方。如果你把dp[i][j]理解为“前i个字符对应前j个字符”那边界初始化就很容易出错如果定义为“长度”初始化就清晰了dp[0][j] j因为从空串变成任意长度为j的字符串只能靠插入j个字符dp[i][0] i因为从长度为i的字符串变成空串只能靠删除i个字符。4.2 状态转移方程推导接下来是转移方程。对于dp[i][j]我们要分两种情况看。第一种情况是word1[i-1] word2[j-1]也就是当前这两个字符相等。此时不需要额外操作dp[i][j]直接等于dp[i-1][j-1]。第二种情况是字符不相等我们有三种操作可以考虑替换把word1[i-1]替换成word2[j-1]操作数1问题变成dp[i-1][j-1] 1。删除把word1[i-1]删掉操作数1问题变成dp[i-1][j] 1。插入在word1的当前位置插入word2[j-1]操作数1问题变成dp[i][j-1] 1。取三者最小值就行。举个例子word1 horseword2 ros我们要求dp[5][3]。依次填表最终会得到3。完整DP代码def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] 1 min( dp[i - 1][j], # 删除 dp[i][j - 1], # 插入 dp[i - 1][j - 1] # 替换 ) return dp[m][n]时间复杂度和空间复杂度都是O(m×n)。如果你在面试里写了这个版本已经可以过关了。但能说清楚“为什么需要m1和n1”的维度以及“为什么字符相等时直接取左上”说明你是真的理解了。4.3 滚动数组空间优化和第70题类似第72题也做空间优化。观察转移方程能发现dp[i][j]只依赖三格左边dp[i][j-1]、上边dp[i-1][j]、左上dp[i-1][j-1]。这意味着我们不需要保存整个二维表只需要上一行和当前行甚至可以用一维数组加一个额外变量来完成。滚动数组版本def minDistance_optimized(word1: str, word2: str) - int: m, n len(word1), len(word2) if m n: word1, word2 word2, word1 m, n n, m dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if word1[i - 1] word2[j - 1]: dp[j] prev else: dp[j] 1 min(dp[j], dp[j - 1], prev) prev temp return dp[n]这里有一个小细节我先把word1换成长度更长的那一个让外层循环次数更多、内层数组长度更短这样空间消耗更小。这在理论上只是小优化但对理解“DP的空间维度其实可以选”这件事很有帮助。4.4 面试中的追问方向第72题在面试里经常被继续追问最常见的几个方向是优化到O(min(m,n))空间也就是上面的滚动数组版本。输出具体的编辑操作步骤而不只是次数。这要求在填表时额外记录每个格子的操作类型最后从dp[m][n]回溯到dp[0][0]。如果三种操作的代价不一样怎么办比如插入代价是2删除是1替换是3转移方程里的三个“1”就要改成各自对应的代价。这是编辑距离的实际应用版本。“输出具体操作步骤”这个追问我特别建议自己动手实现一遍。回溯过程有点绕但做完之后你对二维DP表的理解会深一个层次。5. 实测校验与排错方法5.1 常见报错与排查思路这三题虽然逻辑都不算复杂但在提交时还是有不少高频报错。第70题最常见的报错是n0和n1边界。LeetCode给的范围是1 n 45所以有些解法不处理n0也能过但如果你把代码迁移到别的场景n0很可能就出错了。我在面试中被问到过n0应该返回多少按照题目语义0阶台阶应该返回1因为“什么都不做”也是一种方法。LeetCode原题没有覆盖到这个值但实际工程里要明确。第71题最容易在返回拼接时出错。很多人最后写return .join(stack)结果丢了开头的/或者把空栈的情况拼成而不是/。建议写完后专门跑一遍输入为/或/../的用例。第72题的高频坑在初始化。如果你把dp[0][0]忘了设成0后面的结果会全部偏移。还有人喜欢在Python里用[[0] * (n1)] * (m1)建二维数组这样做非常危险因为m1行会指向同一个列表对象改一个就等于改所有行。我第一次写就踩过这个坑排查了很久才发现是数组初始化的问题。5.2 一套可复用的调试流程这里分享一个我平时调试DP题的固定流程对三道题都适用。第一先构造一个规模足够小、能手工验证的用例。比如第70题取n5预期是8第71题取/a/./b/../../c/预期是/c第72题取word1horse, word2ros预期是3。小用例能让你在出错时快速定位是哪一步状态转移不对。第二打印中间状态。第70题打印每个i对应的dp[i]第71题打印每一轮操作后栈的内容第72题打印整个二维表。DP题的一大特点是“局部正确不代表全局正确”打印中间状态能把出错的那一格直接暴露出来。第三对照状态转移方程逐格推演。比如第72题算出来的dp[2][1]和你手工推的不一致就停下来检查当前字符是否相等、三个来源的方向有没有写错。这个排查过程比反复提交代码要高效得多。5.3 当天刷题的复盘记录三道题全部提交通过后我会习惯性地做一个复盘核心只有三个问题每道题的解法最关键的突破点是什么如果换一个输入规模解法要做什么调整哪些题可以归并到同一类解法体系里第70题的关键突破点是“最后一步从哪里来”第71题的关键是“路径处理规则等价于栈的压弹逻辑”第72题的关键是“怎么把字符串转换问题拆成子问题”。三题看起来解法完全不同但底层思维是相通的都在定义“当前状态和前一个或几个状态的关系”只不过第71题用栈显式维护状态第70、72题用DP数组隐式维护状态。个人经验上这类题目当天刷完一定要再花时间做二刷标记尤其是第72题我第一次做需要四十分钟二刷只用了十五分钟三刷的时候基本就是默写状态转移方程了。你可能觉得重复刷没意思但算法能力的提升恰恰就来自这种“从陌生到熟练”的过程。最后再分享一个小技巧很多人喜欢把中等题和困难题堆在一起刷我反而不太推荐。像今天这样“一简一中小难”的配比对我来说节奏刚好既能保证动手量又不会让脑子过载。你可以根据自己的水平调整但无论如何刷完后的复盘一定要做否则这一天的题等于白刷。 2月12日这天我按计划刷完了LeetCode的70、71、72三道题。说实话这几道题很多刷题攻略都建议分开练但我偏偏把它们排在了一起原因很简单这三题恰好串起了一条从一维DP到栈模拟再到二维DP的能力递进线。一天之内连续啃下来比分散在三天刷的收获要大得多。这篇文章就把当天我自己的做题思路、代码实现、踩坑过程完整记录下来给同样在按题号刷题的朋友做一个参考。先说清楚这三道题分别是什么70. 爬楼梯每次可以爬1阶或2阶问爬到第n阶有多少种不同方法。71. 简化路径给定Unix风格的绝对路径要求简化成规范路径。72. 编辑距离计算把一个单词转换成另一个单词所需的最少操作次数操作包括插入、删除、替换。三道题里有两道是动态规划一道是栈模拟。如果你刚开始学算法或者正在准备面试这三题都是非常典型的训练样本。下面我按当天做题的顺序把每一步思考过程都展开讲。1. 为什么把这三道题放在同一天刷1.1 题目本身是什么先给没刷过这些题的朋友快速解释一下题目背景。爬楼梯的问题实际上问的是“n阶楼梯一次跨1步或2步总共有多少种上楼方式”。这是一个非常经典的动态规划入门题很多教材都会用斐波那契数列来引入。简化路径问题输入类似/a/./b/../../c/这样的字符串要求按照Unix路径规则化简。过程中有两个关键规则.表示当前目录直接忽略..表示返回上一级目录需要弹出当前目录。编辑距离问题要求计算两个字符串之间的最小编辑距离。比如把horse变成ros最少需要三步。这道题是文本相似度、拼写纠错、基因序列比对等领域的基础模型。1.2 三题之间的能力递进关系把这三题放在一起最核心的原因是它们形成了一个能力梯度。第70题只涉及一个状态维度也就是“当前在第几阶”状态转移是线性的适合作为动态规划的“热身运动”。第72题则把状态变成二维同时还需要考虑三个方向的转移来源难度明显上升。而第71题虽然不涉及DP却考察了字符串处理和栈这个数据结构的边界处理能力。这种“一维DP 栈模拟 二维DP”的组合正好覆盖了面试算法题里的几大高频考点。一天之内连续接触三种不同思想记忆会更深刻尤其是第70题和第72题之间的对比能让你直观感受到“从一维到二维”的DP思维变化。1.3 每日刷题量的安排逻辑很多人刷题容易陷入两个极端一是每天只刷一道简单题没有压力也没有提升二是追求题量一天刷十道结果每道都是抄答案。我的经验是每天三到四题是比较合适的量而且这三四题之间最好有内在关联。比如今天安排70、71、72原因就是它们的“解法血缘”有关系第70题和第72题都是DP但状态规模不一样第71题是栈但它和第70题有共同点都涉及“当前位置的前后依赖”只是实现手段不同。这样安排你在刷完第70题后进入第71题的栈世界再带着这种状态去看第72题会更清楚不同数据结构和DP分别适合解决什么问题。2. 第70题爬楼梯——动态规划的热身2.1 题意与切入点题目说得很直白你站在楼梯底部要走到第n阶每一步可以走1阶或2阶问走法总数。我第一次遇到这题时第一反应是递归枚举所有走法于是写了一个climbStairs(n) climbStairs(n-1) climbStairs(n-2)。这个式子本身是对的但直接递归会导致大量重复计算。比如算n10climbStairs(8)会被重复调用很多次。这在LeetCode上会超时。正确的切入点是意识到这个递推关系和斐波那契数列完全一致只不过初始值不同。到第1阶只有1种走法到第2阶有2种走法于是从第3阶开始每一阶的走法数等于前两阶之和。2.2 从递归到记忆化再到迭代很多人会直接背DP写法但我的建议是先把递归思路走一遍再做优化。递归的思路就是从终点往回推要到达第n阶最后一步要么从第n-1阶跨1阶过来要么从第n-2阶跨2阶过来。所以到达第n阶的总方法数就是把到达第n-1阶和第n-2阶的方法数相加。def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这个版本用一个数组存下了每一步的答案时间复杂度O(n)空间复杂度O(n)。如果继续优化会意识到我们每次只用到了前两个状态所以没必要保留整个数组用两个变量滚动更新就行。def climbStairs_optimized(n: int) - int: if n 2: return n prev, cur 1, 2 for _ in range(3, n 1): prev, cur cur, prev cur return cur空间从O(n)降到了O(1)。这种滚动数组的优化思路在后面第72题里还会用上所以刷这题时一定要把“为什么可以只保留前两个值”想透彻。2.3 复杂度分析与变形题这一题的标准时间复杂度是O(n)如果遇到n特别大的场景比如n达到10的18次方还可以用矩阵快速幂把复杂度降到O(logn)或者直接用斐波那契通项公式。面试中一般不要求但提一嘴会让面试官觉得你知识面广。第70题最常见的变形包括一次可以爬1、2、3阶有一个台阶不能踩最少跳几次能到顶。这些变形都有一个共同点就是状态转移关系仍然是根据“最后一步从哪里来”反推。只要掌握这个分析套路变形题都不会太难。提示如果你刷这题时觉得“递推式好简单但还是不知道自己怎么写出来的”建议拿一张纸把n1到n5的走法全部列出来再对照代码看一遍。这个题目虽然简单但它是理解DP“状态定义”和“转移方程”之间关系的最好入门素材。3. 第71题简化路径——用栈处理字符串3.1 题意与边界陷阱第71题是一道看起来很繁琐、但解法非常固定的题。输入是Unix风格绝对路径例如/a/./b/../../c/输出要求是规范化后的路径规则有三条多个连续/只保留一个。.表示当前目录直接忽略。..表示回到上一级目录如果已经在根目录则忽略。这道题的核心不是“会不会栈”而是“能不能把所有边界情况一次性想清楚”。我见过很多人代码写对了但在/../这种输入上翻车还有人在/a//b这种连续斜杠上出错。3.2 栈模拟的完整过程解法用栈非常自然把路径按/切分成若干段遍历每一段根据段内容决定是压栈、弹栈还是跳过。def simplifyPath(path: str) - str: stack [] for part in path.split(/): if part or part .: continue if part ..: if stack: stack.pop() else: stack.append(part) return / /.join(stack)这里的关键细节是path.split(/)。比如输入/a//b按/切分后得到[, a, , b]空字符串会被忽略掉所以连续斜杠不会造成问题。输入/a/./b会得到[, a, ., b].也被忽略。输入/a/../b会得到[, a, .., b]遇到..时把栈里的a弹掉最后只剩b。我实际写的时候发现Python里split真的好用但如果你用C或者Java需要注意split函数的边界行为Java的split会保留前导空字符串C的std::getline处理起来稍麻烦。任何语言核心逻辑都是同一套。3.3 常见错误与边界用例这题的高频错误主要有三个没有处理..在根目录的情况比如/../正确输出是/不是//或者报错。根据规则栈为空时遇到..应该直接忽略。最后拼接路径时忘记加开头的/。比如栈里最后是[a, b]正确结果是/a/b没有开头斜杠是错的。把...当成..处理。注意只有恰好两个点的字符串才是“返回上级目录”...是合法的目录名。我建议刷这题时多跑几个边界用例至少要把/home/、/../、/home//foo/、/a/./b/../../c/、/.../a这五种情况都验证一遍。尤其是最后一个/.../a...要当成普通目录名压栈很多题解没提这个点但这个恰恰是面试官爱挖的坑。4. 第72题编辑距离——二维DP的经典模型4.1 题意与状态定义编辑距离这题我第一次看的时候被“编辑距离”四个字吓到了觉得很高深。实际上它要解决的问题是给定两个字符串word1和word2每次可以对word1做三种操作之一插入一个字符、删除一个字符、替换一个字符问最少需要多少次操作能让word1变成word2。这道题的关键是定义DP状态。我用dp[i][j]表示“把word1的前i个字符转换成word2的前j个字符所需的最少操作次数”。注意这里i和j指的不是字符下标而是长度。比如word1 horseword2 rosdp[3][2]表示把hor变成ro的最少步数。这个状态定义是很多新人最容易卡住的地方。如果你把dp[i][j]理解为“前i个字符对应前j个字符”那边界初始化就很容易出错如果定义为“长度”初始化就清晰了dp[0][j] j因为从空串变成任意长度为j的字符串只能靠插入j个字符dp[i][0] i因为从长度为i的字符串变成空串只能靠删除i个字符。4.2 状态转移方程推导接下来是转移方程。对于dp[i][j]我们要分两种情况看。第一种情况是word1[i-1] word2[j-1]也就是当前这两个字符相等。此时不需要额外操作dp[i][j]直接等于dp[i-1][j-1]。第二种情况是字符不相等我们有三种操作可以考虑替换把word1[i-1]替换成word2[j-1]操作数1问题变成dp[i-1][j-1] 1。删除把word1[i-1]删掉操作数1问题变成dp[i-1][j] 1。插入在word1的当前位置插入word2[j-1]操作数1问题变成dp[i][j-1] 1。取三者最小值就行。举个例子word1 horseword2 ros我们要求dp[5][3]。依次填表最终会得到3。完整DP代码def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] 1 min( dp[i - 1][j], # 删除 dp[i][j - 1], # 插入 dp[i - 1][j - 1] # 替换 ) return dp[m][n]时间复杂度和空间复杂度都是O(m×n)。如果你在面试里写了这个版本已经可以过关了。但能说清楚“为什么需要m1和n1”的维度以及“为什么字符相等时直接取左上”说明你是真的理解了。4.3 滚动数组空间优化和第70题类似第72题也做空间优化。观察转移方程能发现dp[i][j]只依赖三格左边dp[i][j-1]、上边dp[i-1][j]、左上dp[i-1][j-1]。这意味着我们不需要保存整个二维表只需要上一行和当前行甚至可以用一维数组加一个额外变量来完成。滚动数组版本def minDistance_optimized(word1: str, word2: str) - int: m, n len(word1), len(word2) if m n: word1, word2 word2, word1 m, n n, m dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if word1[i - 1] word2[j - 1]: dp[j] prev else: dp[j] 1 min(dp[j], dp[j - 1], prev) prev temp return dp[n]这里有一个小细节我先把word1换成长度更长的那一个让外层循环次数更多、内层数组长度更短这样空间消耗更小。这在理论上只是小优化但对理解“DP的空间维度其实可以选”这件事很有帮助。4.4 面试中的追问方向第72题在面试里经常被继续追问最常见的几个方向是优化到O(min(m,n))空间也就是上面的滚动数组版本。输出具体的编辑操作步骤而不只是次数。这要求在填表时额外记录每个格子的操作类型最后从dp[m][n]回溯到dp[0][0]。如果三种操作的代价不一样怎么办比如插入代价是2删除是1替换是3转移方程里的三个“1”就要改成各自对应的代价。这是编辑距离的实际应用版本。“输出具体操作步骤”这个追问我特别建议自己动手实现一遍。回溯过程有点绕但做完之后你对二维DP表的理解会深一个层次。5. 实测校验与排错方法5.1 常见报错与排查思路这三题虽然逻辑都不算复杂但在提交时还是有不少高频报错。第70题最常见的报错是n0和n1边界。LeetCode给的范围是1 n 45所以有些解法不处理n0也能过但如果你把代码迁移到别的场景n0很可能就出错了。我在面试中被问到过n0应该返回多少按照题目语义0阶台阶应该返回1因为“什么都不做”也是一种方法。LeetCode原题没有覆盖到这个值但实际工程里要明确。第71题最容易在返回拼接时出错。很多人最后写return .join(stack)结果丢了开头的/或者把空栈的情况拼成而不是/。建议写完后专门跑一遍输入为/或/../的用例。第72题的高频坑在初始化。如果你把dp[0][0]忘了设成0后面的结果会全部偏移。还有人喜欢在Python里用[[0] * (n1)] * (m1)建二维数组这样做非常危险因为m1行会指向同一个列表对象改一个就等于改所有行。我第一次写就踩过这个坑排查了很久才发现是数组初始化的问题。5.2 一套可复用的调试流程这里分享一个我平时调试DP题的固定流程对三道题都适用。第一先构造一个规模足够小、能手工验证的用例。比如第70题取n5预期是8第71题取/a/./b/../../c/预期是/c第72题取word1horse, word2ros预期是3。小用例能让你在出错时快速定位是哪一步状态转移不对。第二打印中间状态。第70题打印每个i对应的dp[i]第71题打印每一轮操作后栈的内容第72题打印整个二维表。DP题的一大特点是“局部正确不代表全局正确”打印中间状态能把出错的那一格直接暴露出来。第三对照状态转移方程逐格推演。比如第72题算出来的dp[2][1]和你手工推的不一致就停下来检查当前字符是否相等、三个来源的方向有没有写错。这个排查过程比反复提交代码要高效得多。5.3 当天刷题的复盘记录三道题全部提交通过后我会习惯性地做一个复盘核心只有三个问题每道题的解法最关键的突破点是什么如果换一个输入规模解法要做什么调整哪些题可以归并到同一类解法体系里第70题的关键突破点是“最后一步从哪里来”第71题的关键是“路径处理规则等价于栈的压弹逻辑”第72题的关键是“怎么把字符串转换问题拆成子问题”。三题看起来解法完全不同但底层思维是相通的都在定义“当前状态和前一个或几个状态的关系”只不过第71题用栈显式维护状态第70、72题用DP数组隐式维护状态。个人经验上这类题目当天刷完一定要再花时间做二刷标记尤其是第72题我第一次做需要四十分钟二刷只用了十五分钟三刷的时候基本就是默写状态转移方程了。你可能觉得重复刷没意思但算法能力的提升恰恰就来自这种“从陌生到熟练”的过程。最后再分享一个小技巧很多人喜欢把中等题和困难题堆在一起刷我反而不太推荐。像今天这样“一简一中小难”的配比对我来说节奏刚好既能保证动手量又不会让脑子过载。你可以根据自己的水平调整但无论如何刷完后的复盘一定要做否则这一天的题等于白刷。