爬楼梯与动态规划：从LeetCode 70到一维DP通用解法

1. 从“爬楼梯”看动态规划的本质1.1 一道题为什么能被力扣列为动态规划入门首选LeetCode 70题 Climbing Stairs爬楼梯常年霸榜在“简单题”分类里但它的地位却一点不简单。几乎所有刷题攻略、算法课程、面试经验帖都会把这道题放在动态规划的第一站地位和二分查找里的 Binary Search、链表里的 Reverse Linked List 差不多。你需要知道的是这道简单题背后藏着一整套一维动态规划的分析框架把这个框架吃透了后面再做“打家劫舍”“跳跃游戏”“零钱兑换”“最长递增子序列”这些经典题会顺畅很多。题目原文其实不复杂你正在爬楼梯楼梯有 n 阶每次可以爬 1 阶或 2 阶那么到楼顶一共有多少种不同的爬法约束条件里 n 是正整数。比如 n2 时你可以一次跨 1 阶再跨 1 阶也可以直接跨 2 阶所以答案是 2 种n3 时有 111、12、21 这 3 种。第一次看到这个题的人很容易陷进“去枚举所有爬法”的思路里试图用递归把所有走法列出来。这个方向不算错但如果你只是想求方案总数枚举就绕远了。动态规划的思路恰恰相反——它不关心每一种具体组合长什么样只关心“到达每一阶的方案数”之间存在什么样的递推关系。这种视角的转换就是动态规划和暴力枚举最本质的区别。1.2 为什么这道题是“一维动态规划”的典型代表动态规划按状态的维度分常见的有“一维 DP”和“二维 DP”。一维 DP 通常只需要一个一维数组甚至几个变量来存储状态状态之间通过一条清晰的递推关系串联起来二维 DP 则一般涉及两个维度比如两个字符串的编辑距离、矩阵路径问题状态一般要开一个二维数组。Climbing Stairs 是典型的一维 DP状态定义就是 dp[i]表示爬到第 i 阶楼梯有多少种不同的方法。你只需要维护这一个数组不需要第二层维度。它非常适合用来学“状态设计 状态转移方程”这套方法论因为问题足够简单不会在理解题意上浪费时间递推关系非常直观可以从实际爬法推导出来不需要高深的数学基础边界条件少而且明确适合练习初始化最终代码量极小但优化空间很大从递归到记忆化再到数组滚动思路层层递进。所以如果你刚开始接触动态规划我强烈建议把这道题作为第一个亲手推演、亲手写代码的样本。别着急去看别人的题解先自己画一画、算一算把“为什么第 i 阶的方案数等于第 i-1 阶方案数加第 i-2 阶方案数”彻底想明白比多刷十道题都值。2. 核心思路拆解从暴力递归到递推公式2.1 先画一个“递归树”看清问题结构我上手任何一道 DP 题第一件事不是在脑子里套模板而是先手工推演几个小规模的例子。以 n5 为例把所有爬法想象成一棵递归树从第 0 阶出发第一步可以爬 1 阶到第 1 阶也可以爬 2 阶到第 2 阶到达第 1 阶后又可以选择再爬 1 阶到第 2 阶或者再爬 2 阶到第 3 阶依次类推直到到达第 5 阶。这棵树往下展开你会发现很多“子树”是完全重复的。比如从第 3 阶到第 5 阶的爬法无论你是通过哪种途径到达第 3 阶的后续的选择都一样。这就意味着在暴力枚举的过程中计算 f(3) 会被反复执行很多次整个算法的耗时呈指数增长。计算一下递归节的复杂度如果定义 f(n) 为爬到第 n 阶的方案数那么 f(n) f(n-1) f(n-2)递归出口是 f(1)1、f(2)2。这样递归下去函数调用次数大约是 2^n 的规模。n 稍大一点比如 n40程序就已经肉眼可见地卡顿。这不是代码写得不好而是算法设计本身存在大量重复子问题。2.2 递推公式的推导为什么是 f(n) f(n-1) f(n-2)这个递推公式我用一句话说明白你最后一次迈步只有两种可能要么是从第 n-1 阶跨 1 阶上来的要么是从第 n-2 阶直接跨 2 阶上来的。而“爬到第 n-1 阶的方案数”加上“爬到第 n-2 阶的方案数”就是“爬到第 n 阶的方案数”。听起来像是废话但它正是动态规划的核心动作把一个规模较大的问题拆成两个规模较小、且结构和原问题完全一致的子问题。这种“原问题和子问题拥有相同性质”的特点决定了我们可以使用 DP 来解决而不是另起炉灶重新建模。我建议你自己动手列一下n1只有 1 种直接爬 1 阶n2有 2 种11 或直接 2n3从 n1 过来有 f(1)1 种从 n2 过来有 f(2)2 种合计 3 种n4从 n2 过来有 f(2)2 种从 n3 过来有 f(3)3 种合计 5 种n5f(3)f(4)358 种。看到 1、2、3、5、8 这个数列对数列敏感的人马上会意识到这不就是斐波那契数列吗对Climbing Stairs 本质上就是斐波那契数列的翻版只是初始项不同。斐波那契是 F(0)0、F(1)1而本题是 f(1)1、f(2)2。理解这一点后这道题的数学底牌就亮出来了但实际工程中我们一般不直接去套斐波那契的通项公式而是仍然用递推来解决问题因为递推的时间和空间最容易控制也最容易通过代码审查。2.3 “动态规划五步法”解决一切 DP 题的心法我刷题这么多年最受用的不是记住某个题的解法而是形成一套固定的分析框架。这里分享一个自己一直在用的“动态规划五步法”每一步都可以对应到本题中第一步确定 dp 数组及下标的含义。本题中 dp[i] 表示爬到第 i 阶的方法总数。第二步确定递推公式。dp[i] dp[i-1] dp[i-2]。这是整个公式体系的核心推导过程前面已经讲过了。第三步dp 数组如何初始化。本题的实际含义中dp[1] 11 阶楼梯只有 1 种爬法dp[2] 22 阶楼梯有 2 种爬法。数组下标从 0 开始的话可以令 dp[0] 1为了让 dp[2] dp[1] dp[0] 成立。这里有种说法dp[0] 表示“原地不动”也可以理解成一种方案这样递推才自洽。有些资料从 dp[0]1 开始这里需要你注意主流题解里用 dp[0]1 或直接跳过 dp[0] 都行但逻辑要自洽最好自己先定好下标从 0 开始还是从 1 开始。第四步确定遍历顺序。显然应该从前往后遍历因为 dp[i] 依赖 dp[i-1] 和 dp[i-2]必须保证在计算 dp[i] 时所依赖的子状态已经算好了。第五步打印/推演 dp 数组看是否正常。遇到报错或者答案不对时把 dp 数组打印出来和手推的结果对照是最快的排错方式。这个方法不仅适用于 Climbing Stairs后面你遇到的所有 DP 题都可以按这个套路来。熟练之后“五步法”会变成你的肌肉记忆看到题目能快速在脑中走完一遍。3. 三种解法横向对比暴力递归、记忆化递归、自底向上动态规划3.1 解法一暴力递归理解问题但不可用暴力递归的代码非常短但性能极差def climb_stairs_brute(n): if n 2: return n return climb_stairs_brute(n-1) climb_stairs_brute(n-2)时间复杂度 O(2^n)空间复杂度 O(n)系统递归栈的深度。实际跑起来 n35 的时候已经很吃力n45 基本没法接受。它存在的原因是能让初学者快速验证递推公式的正确性但工程上毫无意义。不过有一点值得说递归版本是“自上而下”的思维。你先想“到达 n 阶有多少种”然后拆成“到达 n-1 阶”和“到达 n-2 阶”一路拆到最小的子问题。这个思维转换在 DP 里叫“递归的直觉”是多数人最容易理解的起点。有了这个起点才能往下一步优化。3.2 解法二记忆化递归常规优化但空间不够极致记忆化递归的思路很朴素既然暴力递归会反复计算同一个子问题那就用一个数组把已经算过的结果存下来下次直接用。def climb_stairs_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 2: return n memo[n] climb_stairs_memo(n-1, memo) climb_stairs_memo(n-2, memo) return memo[n]时间复杂度 O(n)每个子问题只计算一次空间复杂度 O(n)因为需要一个哈希表或数组存储 n 个状态再加上递归栈。这种方式在实际刷题中经常用到它的优点是保留了递归的直观结构缺点是在空间上没有做到最优。3.3 解法三自底向上动态规划最推荐的工程写法自底向上的 DP 是从最小状态出发依次推导到目标状态。先算 dp[1]、dp[2]再用递推公式计算 dp[3]一直到 dp[n]。def climb_stairs_dp(n): if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]时间复杂度 O(n)空间复杂度 O(n)。这是第一次接触 DP 的读者应该掌握的版本因为它把“状态数组”这个概念完整暴露了出来方便你对着数组下标和值理解递推过程。等你完全掌握之后再进一步做空间优化因为 dp[i] 只依赖前两个状态没必要保留一整张表直接用两个变量滚动更新即可。3.4 空间优化从 O(n) 到 O(1) 的滚动思想滚动数组优化我觉得是这道题里最妙的一步它体现的思维在后续很多 DP 题里都会用到def climb_stairs_optimized(n): if n 2: return n prev2, prev1 1, 2 for i in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1这里 prev2 代表 dp[i-2]prev1 代表 dp[i-1]每次循环把状态往前滚动一位。空间复杂度降为 O(1)时间复杂度仍然是 O(n)。你可能会说内存省这一点有什么意义在力扣这种限时受限空间的评测系统里确实意义不大但写代码的时候习惯性地考虑空间优化是一个工程师的基本素养。更重要的是滚动数组思想在“背包问题”“最长回文子串”等高级题目里经常出现提前在这道简单题里培养意识后面会省很多力气。这里分享一个我在面试现场遇到过的情况候选人能很快写出 dp 数组版本但问“能不能把空间压缩到 O(1)”时卡住了。这道题作为面试开场题面试官往往不只是看你能否 AC更想看你能不能在讲清楚复杂度之后进一步优化空间。所以我建议你这四种形式都要能手写出来并且能解释清楚每一步为什么可以这样做。3.5 三种方案复杂度对照速查表为了方便你记忆和复习我整理了一张对照表方案时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)仅用于理解递推关系不用于实际解题记忆化递归O(n)O(n)适合保留递归思维习惯时写面试时也可以提一句自底向上 DPO(n)O(n)入门推荐状态清晰方便排错滚动数组 DPO(n)O(1)工程和面试最佳选择需要能熟练写出来4. 完整实操过程从理解题意到 AC 全流程4.1 动手前的准备工作边界条件与规模预判在力扣上做题拿到题目后别急着写代码。我先检查几个要素一是 n 的取值范围。力扣原题约束是 1 n 45。这个范围意味着最坏情况时答案是多少提前算一下可以帮你判断结果需要用什么类型存储。当 n45 时可能的结果是 1836311903恰好小于 32 位有符号整数的上限 2147483647所以在 C 中用 int 就够了Python 则无所谓因为 Python 的 int 是任意精度。但如果你自己改编题目把 n 的范围扩大比如 n100那结果会变成 573147844013817084101远超 64 位整数范围。这时候就要考虑大数类型或用模数取余了。力扣原题的约束不大但养成先看数据范围、预估结果量级的好习惯能帮你少踩很多坑。二是边界情况。n1 时直接返回 1 就行n2 时返回 2。很多人在写 dp[2] 时想当然在循环里统一处理 n1、n2就会出现数组越界。所以代码里先判空、先处理边界是我在每一道题里都坚持做的习惯。4.2 逐行手写实现以 Python 和 C 为例先说 Python 版本。刚才已经给出了 dp 版本和滚动数组版本这里我再补充一个我个人在实际刷题中比较喜欢写的“列表推导 预分配”的版本class Solution: def climbStairs(self, n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这个版本的优点是结构清晰面试时方便逐步讲给面试官听。你甚至可以一边讲“这是我的 dp 数组下标表示第几阶台阶值表示方法数”一边写出递推公式整个过程会显得非常严谨。C 版本同样简单class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorint dp(n 1, 0); dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };如果你是在面试中写 C回答完这个版本后紧接着可以展示“空间优化版本”class Solution { public: int climbStairs(int n) { if (n 2) return n; int prev2 1, prev1 2, cur; for (int i 3; i n; i) { cur prev1 prev2; prev2 prev1; prev1 cur; } return prev1; } };大多数人默认 Python 写起来更短但 C 版本也没有长多少。面试时我建议先写出 dp 数组的版本因为你可以在写的过程中把“为什么 dp[i] dp[i-1] dp[i-2]”讲一遍同时看一眼面试官是不是跟得上。等对方点头了再去主动提空间优化这是加分的节奏。4.3 在力扣上提交的完整流程与踩坑记录在力扣上提交这道题一般顺利但我也见过几位同学卡过一些莫名其妙的地方这里统一列一下第一坑数组长度开成 n 而不是 n1。如果你声明 vector dp(n)然后访问 dp[n]直接越界。下标从 1 开始使用时记得长度是 n1。类似的问题在 Python 里也一样[0] * n以后dp[n] 就超出范围了。第二坑没有处理 n1 的情况。这里不是说一定会报错而是当 n1 时如果你直接给 dp[2] 赋值就先越界了。所以在循环之前先把if n 2的边界切断养成习惯。第三坑Python 的递归写法超过递归深度。有的同学用lru_cache装饰器写记忆化递归一切正常但如果直接写裸递归且 n45大概率会报递归深度错误RecursionError。虽然这个问题在本题的力扣测试集里不一定会出现但平时练习时最好养成用循环的习惯不要把递归深度当成隐形的坑。第四坑误用矩阵快速幂。这题确实可以用斐波那契通项公式或矩阵快速幂来解时间复杂度能到 O(log n)但力扣的 n 上限是 45根本不需要这种优化。不过作为扩展视野可以了解一下“斐波那契数列 快速幂”的思路面试时主动讲出来会显得你有广度。4.4 如何验证自己写的代码是正确的很多初学者写完代码后直接点提交AC 了就万事大吉。其实更好的做法是在本地先手动验证几个值因为提交上去一旦报错你只知道“答案错误”还得回过头来调试不如先自测。我常用的一组自测数据是n1期望输出 1n2期望输出 2n3期望输出 3n4期望输出 5n5期望输出 8n6期望输出 13。这组数据从 1 到 6 恰好是斐波那契数列从第 2 项开始的连续 6 个值。跑对了这组基本可以放心提交。如果面试时面试官要求你验证算法的正确性这个方法也很有说服力因为你展示的不仅是代码能跑还展示了你对输入和输出之间关系的理解。4.5 从 AC 到深度理解一道题的价值延伸提交通过不等于掌握。很多刷题博主都会讲“二刷三刷”的重要性而我认为至少做到以下几点才叫真正“吃透”了 Climbing Stairs能不看答案在 3 分钟内写出滚动数组版本能清楚讲出“为什么 dp[i] dp[i-1] dp[i-2]”的物理含义能自行扩展到“每次可以爬 1、2、3 阶”的变体——此时递推方程变成 dp[i] dp[i-1] dp[i-2] dp[i-3]初始条件相应调整能看懂并讲出矩阵快速幂的做法虽然不一定用得上能联想到其他一维 DP 题里的类似状态转移结构比如“使用最小花费爬楼梯”力扣 746 题。第 3 点很值得你亲手做一遍。把步长从 2 改成 3实际上是同一个套路但它能帮你确认自己是真的理解了递推方程的来源而不是死记硬背。第 5 点则是你把单题经验抽象成“一类题”的关键一步。这道题是“加法型”递推而“打家劫舍”是“选或不选”的决策型递推结构上很像但状态转移的写法有微妙差异。在题目之间建立联系比刷题数量更重要。5. 常见问题与排错实录5.1 输出斐波那契数列却不知道错在哪有一个很常见的问题有同学写完答案后发现输出和斐波那契数列从“0、1、1、2、3、5”对不上就开始怀疑自己代码写错了。其实这里要注意Climbing Stairs 从 f(1)1、f(2)2 开始它其实是斐波那契数列的“错位”版本。如果你硬套 Fibonacci 的标准实现F(0)0、F(1)1那么你会发现标准斐波那契F(0)0, F(1)1, F(2)1, F(3)2, F(4)3, F(5)5本题的答案序列f(1)1, f(2)2, f(3)3, f(4)5, f(5)8。两者从第 2 项开始关系是 f(n) F(n1)。所以在代码实现时不用硬把斐波那契的初始值套进来直接按题目语义定义 dp[1] 和 dp[2] 反而更不容易错。5.2 递归超时或栈溢出的排查思路如果你用了递归版本去提交力扣给的 n 最大只有 45可能勉强能过也可能超时。如果你改了题目范围到 100 以上裸递归一定会被卡。这时候要先看是不是没有加记忆化再看递归深度是不是太大。Python 的默认递归深度一般是 1000理论上 n45 不会超过限制但 n 如果扩大到 2000就很可能触发 RecursionError。解决方法是改用循环 DP或者临时提升递归深度限制但这种做法不推荐治标不治本。正确的排查顺序先确认问题规模再确认采用的自上而下还是自下而上最后再想空间优化。不要一上来就怀疑环境问题。5.3 数组越界和初始化遗漏的快速定位技巧我经历了无数次 debug 之后总结出一条简便经验所有包含 dp 数组的题目第一件事检查数组长度和下标的起始位置。如果你从 dp[1] 开始初始化那么数组长度至少是 n1如果你的循环变量 i 从 0 开始那 dp[0] 的语义要想清楚。针对这道题最常见的越界发生在给dp[2]赋值、但数组长度只有 n 或 n1 时。解决办法很简单在一开始就加一个if n 2: return n的守卫这个分支能挡掉所有“数组长度不够”的问题。5.4 一道变体题的实战演练为了检验你是不是真的掌握了核心思路我建议尝试下面这个变体题目假设你每次可以爬 1 阶或 2 阶但不能连续两次都跨 2 阶。问爬到第 n 阶有多少种方法。这个变体一出来一维的普通 dp 数组就不够用了因为你必须记住上一步走的是 1 步还是 2 步才能判断当前能否跨 2 阶这就得引入二维状态上一轮的步长作为第二维。这正是 Climbing Stairs 从“一维 DP”过渡到“带状态约束 DP”的典型例子也是我特别推荐在掌握基础题后去做的事情在原题上加一个限制看看状态定义是否需要调整。通过这样的训练你会逐渐理解“状态设计是 DP 的灵魂”这句话。6. 一维动态规划的通用模式不再止步于爬楼梯6.1 从爬楼梯抽出一维 DP 的标准解题模板在吃透 Climbing Stairs 之后我想帮你把它的解题模式抽象成一张“万能模板”以后遇到新题可以直接套用第一步到第五步第一步提炼状态。如果问题可以按某种“阶段”划分比如台阶数、数组下标、字符串位置往往可以用一维数组 dp[i] 表示某个阶段的最优值或方案数。第二步写递推关系。思考“当前阶段的最优解”怎么从“上一个阶段”或“前面几个阶段”推导过来。在 Climbing Stairs 中是从 i-1 和 i-2 两个阶段转移在“使用最小花费爬楼梯”中是从 dp[i-1] 和 dp[i-2] 加上当前 cost 转移在“打家劫舍”中是从 dp[i-1]不偷当前家和 dp[i-2] nums[i]偷当前家转移。第三步处理边界和初始值。初始状态必须能手工算出来至少要把 dp[0] 和 dp[1] 定清楚。第四步确定遍历顺序。一维 DP 绝大多数是从左到右少数需要从右到左比如某些背包问题但都是“先算被依赖的状态”。第五步考虑优化空间。如果 dp[i] 只依赖 dp[i-1]、dp[i-2] 这类常数个先前状态就可以用变量滚动优化如果依赖前面所有状态比如“最长递增子序列”里的内层循环那就没法简单滚动需要另想办法。这套流程在面试时非常有用。我见过不少候选人代码写得不熟但思路能按这套模板讲清楚最终面试评价反而比“闷头写对”更高。因为面试官更看重的是你的分析路径而不是答案本身。6.2 力扣上一维 DP 经典题的推荐学习顺序最后分享一个我的刷题顺序建议你想真正把一维动态规划练扎实可以按照下面的顺序从易到难推进第一步力扣 70 题 Climbing Stairs建立递推思想 第二步力扣 746 题 Min Cost Climbing Stairs体会“带成本的状态转移” 第三步力扣 198 题 House Robber理解“选或不选”的决策型 DP 第四步力扣 322 题 Coin Change掌握“最值型递推”和“遍历所有面值”的套路 第五步力扣 300 题 Longest Increasing Subsequence练习“双重循环 状态依赖前面所有状态”的进阶模型。前面两道简单题可以一天内完成后面三道则需要花点时间推演。但只要你把 Climbing Stairs 的“五步法”练成肌肉记忆后面的每一步都会走得比大多数人稳。我个人刷到 300 题时回头总结发现一维 DP 的高频考题几乎都是这些模型的组合或变体极少有跳出这个框架的。所以这题的性价比真的非常高。