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)。这个式子本身是对的，但直接递归会导致大量重复计算。比如算n=10，climbStairs(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阶；有一个台阶不能踩；最少跳几次能到顶。这些变形都有一个共同点，就是状态转移关系仍然是根据“最后一步从哪里来”反推。只要掌握这个分析套路，变形题都不会太难。
提示：如果你刷这题时觉得“递推式好简单，但还是不知道自己怎么写出来的”，建议拿一张纸，把n=1到n=5的走法全部列出来，再对照代码看一遍。这个题目虽然简单，但它是理解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 = "horse"，word2 = "ros"，dp[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 = "horse"，word2 = "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)。如果你在面试里写了这个版本，已经可以过关了。但能说清楚“为什么需要m+1和n+1”的维度，以及“为什么字符相等时直接取左上”，说明你是真的理解了。
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题最常见的报错是n=0和n=1边界。LeetCode给的范围是1 <= n <= 45，所以有些解法不处理n=0也能过，但如果你把代码迁移到别的场景，n=0很可能就出错了。我在面试中被问到过n=0应该返回多少，按照题目语义，0阶台阶应该返回1，因为“什么都不做”也是一种方法。LeetCode原题没有覆盖到这个值，但实际工程里要明确。
第71题最容易在返回拼接时出错。很多人最后写return ''.join(stack)，结果丢了开头的/，或者把空栈的情况拼成''而不是'/'。建议写完后专门跑一遍输入为/或/../的用例。
第72题的高频坑在初始化。如果你把dp[0][0]忘了设成0，后面的结果会全部偏移。还有人喜欢在Python里用[[0] * (n+1)] * (m+1)建二维数组，这样做非常危险，因为m+1行会指向同一个列表对象，改一个就等于改所有行。我第一次写就踩过这个坑，排查了很久才发现是数组初始化的问题。
5.2 一套可复用的调试流程
这里分享一个我平时调试DP题的固定流程，对三道题都适用。
第一，先构造一个规模足够小、能手工验证的用例。比如第70题取n=5，预期是8；第71题取/a/./b/../../c/，预期是/c；第72题取word1="horse", word2="ros"，预期是3。小用例能让你在出错时快速定位是哪一步状态转移不对。
第二，打印中间状态。第70题打印每个i对应的dp[i]；第71题打印每一轮操作后栈的内容；第72题打印整个二维表。DP题的一大特点是“局部正确不代表全局正确”，打印中间状态能把出错的那一格直接暴露出来。
第三，对照状态转移方程逐格推演。比如第72题算出来的dp[2][1]和你手工推的不一致，就停下来检查当前字符是否相等、三个来源的方向有没有写错。这个排查过程比反复提交代码要高效得多。
5.3 当天刷题的复盘记录
三道题全部提交通过后，我会习惯性地做一个复盘，核心只有三个问题：每道题的解法最关键的突破点是什么？如果换一个输入规模，解法要做什么调整？哪些题可以归并到同一类解法体系里？
第70题的关键突破点是“最后一步从哪里来”，第71题的关键是“路径处理规则等价于栈的压弹逻辑”，第72题的关键是“怎么把字符串转换问题拆成子问题”。三题看起来解法完全不同，但底层思维是相通的：都在定义“当前状态和前一个或几个状态的关系”，只不过第71题用栈显式维护状态，第70、72题用DP数组隐式维护状态。
个人经验上，这类题目当天刷完一定要再花时间做二刷标记，尤其是第72题，我第一次做需要四十分钟，二刷只用了十五分钟，三刷的时候基本就是默写状态转移方程了。你可能觉得重复刷没意思，但算法能力的提升恰恰就来自这种“从陌生到熟练”的过程。
最后再分享一个小技巧：很多人喜欢把中等题和困难题堆在一起刷，我反而不太推荐。像今天这样“一简一中小难”的配比，对我来说节奏刚好，既能保证动手量，又不会让脑子过载。你可以根据自己的水平调整，但无论如何，刷完后的复盘一定要做，否则这一天的题等于白刷。
