1. 为什么拿爬楼梯当DP入门题先看它到底在考什么动态规划这名字吓退过很多人我也一样。早些年刷题看到DP两个字母第一反应是“这题是不是得画个状态机”后来刷得多了才明白动态规划真正要解决的问题就三个重叠子问题、最优子结构、状态转移。而LeetCode 70这道爬楼梯题恰好把这三件事都浓缩在一个非常简单的生活场景里所以它成了几乎所有DP入门清单上的第一题。题目本身一句话就能说清你正在爬楼梯每次可以走1阶或2阶问爬到第n阶有多少种不同的走法。但这句话背后藏着的东西比表面看起来深得多。很多人第一次做这题第一反应是列组合数比如n5的时候有多少个1和2能凑出5再对每种组合求排列数。这样能做但一旦n变大组合数枚举的量级直接爆炸而且代码写起来非常绕。这道题真正想让你体会的是“当前结果依赖前面几步结果”的递推思维——也就是动态规划最核心的认知模型你不需要从头枚举所有路径你只需要站在当前位置往前看一步或两步。更具体地说动态规划在这道题里的体现是到达第n阶的方法数等于到达第n-1阶的方法数再走一步加上到达第n-2阶的方法数再走两步。这就是递推关系也叫状态转移方程。至于为什么可以这样拆后面我会详细展开。这一层想通了后面做最小花费爬楼梯、不同路径、打家劫舍这些DP题你会发现套路全都一样先定义状态再写转移方程再处理边界。所以这道题适合谁零基础刚接触算法的初学者、想重新梳理DP体系的刷题者、还有面试前想快速过一遍动态规划基础框架的人。它不涉及复杂的数据结构不需要图论基础连数组都可以用两个变量替代却能把DP的骨架完整呈现出来。把这题吃透你得到的不是一个题的答案而是一套可以迁移到其他DP题上的思维框架。2. 状态定义和递推公式爬楼梯的核心其实就是两行代码2.1 从暴力递归到递推公式的思维过程我先带你把思考过程完整走一遍而不是直接丢结论。假设n4你可能很自然地想用变基法把所有由1和2组成的、和为4的序列都列出来。人工枚举的话能列出来1111、112、121、211、22一共5种。但n6的时候你还能靠拍脑袋列全吗这就是暴力枚举的问题——方法是可行的复杂度不友好而且非常容易漏项。换一个角度站在第4级台阶上往前想。到达第4级台阶要么是从第3级跨一步上来的要么是从第2级跨两步上来的。于是到达第4级的方法数 到达第3级的方法数 到达第2级的方法数这个等式的成立条件是所有到达第3级的方法只要最后再跨一步就是到达第4级的一种方法所有到达第2级的方法只要最后跨两步也是到达第4级的一种方法。而且这两个集合没有重叠——因为最后一步的动作不同一步vs两步走法不可能重合也不会漏掉因为最后一步只可能是这两种情况之一。同样的逻辑可以往前套到达第3级 到达第2级 到达第1级到达第2级 到达第1级 到达第0级。这个“当前项由前两项相加”的结构就是斐波那契数列。所以爬楼梯这道题的数学本质是一个位移斐波那契序列初始条件为f(0)1f(1)1然后f(n) f(n-1) f(n-2)。当然也有人把f(0)定义为0、f(1)1、f(2)2写法略有差别但本质完全一样。2.2 dp数组的定义和边界条件如果用标准的动态规划表达我们定义一个数组dp其中dp[i]表示爬到第i阶楼梯有多少种不同的走法。数组长度为n1注意下标从0开始。初始化部分有人会纠结dp[0]等于1还是0。我的建议是从实际含义出发第0阶代表地面起点一种走法就是“什么都不走”所以dp[0]1。这样dp[2]dp[1]dp[0]112正好对应两种走法11和2自洽。如果你非要把dp[0]定义为0那dp[2]dp[1]dp[0]101就不对了所以你还需要单独把dp[2]2写死。两种做法都能AC但我建议新手用dp[0]1的版本所有项都能用统一递推公式不容易出边界问题。递推公式写成代码就是dp[i] dp[i - 1] dp[i - 2];就这么一行。循环从i2开始一直算到in。到这一步第一版代码就可以写出来了。这个版本的空间复杂度是O(n)因为用了长度为n1的数组。2.3 为什么说这题是DP的“最小完备案例”我判断一道题适不适合用来理解DP就看它是否同时具备三个要素状态定义足够简单、转移关系足够清晰、边界条件足够少。爬楼梯恰好三个全占。状态定义简单在一维数组就够下标就是楼梯阶数不需要考虑二维坐标、不需要背包容量和物品两个维度。转移关系清晰在每一步只跟紧挨着的前两项有关一眼就能看懂“加法”为什么成立。边界条件少在只需要初始化dp[0]和dp[1]后面全部交给循环。很多初学者上来就做二维网格题比如不同路径虽然也是入门经典但二维状态对新手来说多了“横纵语义”的理解负担。爬楼梯把维度压到最小你可以把全部注意力放在“为什么当前项等于前两项之和”这一个核心问题上。这个“为什么”真的想明白了DP就不再是玄学而是一种代入感很强的计数方法。3. 代码实现先写老实版本再谈空间压缩3.1 一维数组的标准写法我用C写一版最朴素的实现这也是我建议新手第一遍先写出来的版本class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorint dp(n 1, 0); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };这一版有什么好处好处是数组里每一个位置的计算都被显式存下来了你可以在调试时打印dp数组逐项检查对不对。比如n5时dp数组应该是[1,1,2,3,5,8]一旦发现第4项不是3那说明你前面的逻辑哪里错了排查起来非常直观。不过有两个细节要提醒。一是dp[0]的问题。上面代码里dp[0]1dp[1]1dp[2]dp[1]dp[0]2逻辑完整。如果你改用dp[0]0、dp[1]1、dp[2]2的初始化解法循环也可以从i3开始同样AC但那种写法对新手容易造成理解偏差——你会疑惑dp[0]到底代表什么。所以我个人强烈建议把这题里的dp[0]想成“在地面上一种走法”比想成“没有楼梯”要自然得多。二是n的边界处理。当n0或n1时直接返回n就行n0在实际题目里不会出现题目说n是正整数但写成if (n 2) return n;可以一并兜住n1、n2的边界省得循环里特判。3.2 空间优化把O(n)压缩到O(1)事实上你会发现dp[i]只依赖dp[i-1]和dp[i-2]两个状态更早的数组项在算完之后就再也用不到了。那为什么要保留一个长度为n1的数组没必要。用两个滚动变量就能完成迭代这叫滚动数组思想是DP里极其常用的空间优化手法。代码如下class Solution { public: int climbStairs(int n) { if (n 2) return n; int prev2 1; // dp[0] int prev1 1; // dp[1] int cur; for (int i 2; i n; i) { cur prev1 prev2; prev2 prev1; prev1 cur; } return cur; } };这版的空间复杂度是O(1)时间复杂度仍然是O(n)。如果你面试时先写了数组版本面试官大概率会追问一句“能不能优化空间”这时候把prev2、prev1滚动更新的思路讲清楚印象分会好很多。这里有个常见的坑很多人写滚动更新时会把赋值顺序搞反写成prev1 cur再prev2 prev1结果发现prev2拿到了旧cur整个序列全错了。记住口诀就好先用旧值算新值再往后退一步。cur prev1 prev2然后prev2扔掉最旧的值变成旧prev1prev1变成cur。顺序不能乱。3.3 从滚动数组进一步想到的矩阵快速幂聊到这我想多说一句因为这道题和斐波那契数列的关系太紧密很多刷题经验丰富的人会直接跳到矩阵快速幂把时间复杂度压到O(log n)。矩阵快速幂的基本思路是斐波那契递推可以写成2×2矩阵的形式然后用矩阵乘法的结合律做快速幂。但对入门DP的读者我不建议在爬楼梯这道题上花时间研究矩阵快速幂。原因很简单它虽然能优化复杂度但引入的数学概念矩阵乘法、快速幂模板会打断你对“状态转移”这个DP核心思想的理解。等你把DP基础打牢再单独立题去练快速幂会轻松得多。这是我个人的真实体会——过早接触进阶优化容易把简单问题复杂化。当然如果你想留着这个知识点做个备忘下面这版用矩阵快速幂求斐波那契的代码可以存下来以后做斐波那契变体题时能用上def mat_mul(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def mat_pow(mat, n): res [[1, 0], [0, 1]] while n: if n 1: res mat_mul(res, mat) mat mat_mul(mat, mat) n 1 return res这只是留作参考不建议入门阶段深究。3.4 大数溢出的边界问题另一个值得提的点是LeetCode 70测试用例最大到n45答案上限是1836311903恰好没超过int32的2147483647所以int类型直接算不会溢出。但如果你把代码放到别的OJ上或者自己把n调大比如n50答案立刻变成12586269025int就炸了。这时候得用long long甚至big int。这个例子说明做题时一定要先确认数据范围。n45和n100的解法难度一样但返回值类型完全不同——面试时如果能主动提一句“这题n的范围决定了用int还是long long”会让面试官觉得你有工程意识不是在机械刷题。4. 变体和进阶爬楼梯的三种常见改法4.1 变体一每次可以爬1阶或3阶这种改法最简单把递推公式里的2改成3就行dp[i] dp[i-1] dp[i-3]。因为最后一步可以是1阶或3阶所以第i阶只能从第i-1阶和第i-3阶转移过来中间的i-2阶你用不上除非允许2阶。边界初始化要小心dp[0]1dp[1]1只能走1阶dp[2]12阶只能11不能直接跨2阶。这种题考的就是你有没有真正理解“最后一步决定了转移来源”而不是死背公式。你把步长集合改成[1, 3]递推关系就跟着变背后的DP思想一点没变。4.2 变体二带代价的爬楼梯LeetCode 746这是爬楼梯最常见的进阶版本数组cost[i]代表爬上第i阶需要支付的费用你可以从第0阶或第1阶开始每次跨1阶或2阶。问到达楼顶的最小花费是多少。状态定义变为dp[i]表示到达第i阶的最小花费转移方程写为dp[i] min(dp[i-1], dp[i-2]) cost[i];含义是到达第i阶所花的总费用等于到达第i-1阶和第i-2阶中的较小者再加上第i阶自己的费用。初始条件dp[0]cost[0]dp[1]cost[1]。楼顶是n阶之外的位置所以答案是min(dp[n-1], dp[n-2])——因为你最后一步可能是从第n-1阶或者第n-2阶直接跨到楼顶不需要再付楼顶的费用。这题依然是爬楼梯的骨架只是把“计数”换成了“最优化”。这也正好回答了动态规划区别于普通递归的一个关键点DP通常处理的是最优化问题或计数问题核心都在递推关系区别在于状态值是累加还是取min。如果你把746做明白了再做打家劫舍相邻两个房子不能同时偷那类题会觉得状态转移的思考方式如出一辙。4.3 变体三完全背包视角的爬楼梯还有一种改法很能打开思路如果每次可以爬1到k阶问有多少种方法。这其实转化成了一个完全背包问题——物品是步长1到k每种步长可以无限使用背包容量是n要求的是装满背包的组合总数。完全背包的写法是外层循环容量、内层循环物品组合数公式dp[j] dp[j - step]。这和原始爬楼梯的“只能取1和2两种物品”完全一致。用背包的视角去理解爬楼梯你会瞬间明白很多DP题其实是同一个模型换层皮。这也是为什么我一直建议入门DP不要贪多把爬楼梯、零钱兑换、不同路径这几道题做透比刷三十道同质题有用得多。5. 从爬楼梯看DP入门的思维陷阱我踩过的那些坑5.1 坑一急着写代码状态没想清楚刚学DP时我有个坏毛病读完题觉得“这好像是个DP”就直接开写循环写到一半发现边界不会初始化。爬楼梯这道题因为太简单这个坏毛病的杀伤力看不出来但一换到复杂题就会翻车。后来我给自己定了个流程先问三个问题。第一dp[i]代表什么第二dp[i]怎么由前面的状态算出来第三dp[0]和dp[1]等于多少三个问题能答上来再开始写代码。爬楼梯这道题就是用来训练这个流程的绝佳素材——你可以在草稿纸上把这三个问题的答案写出来再对照代码就会发现“状态定义清楚之后代码其实很机械”。5.2 坑二把“递推”和“递归”混为一谈很多教材讲DP时会先讲斐波那契数列的递归写法然后说“这样会有大量重复计算所以要用DP优化”。于是有读者就以为DP是递归的进阶版、或者比递归更高级。其实不是。递归是一种函数调用自身的编程技巧DP是一种解决问题的策略。递归实现斐波那契确实简单但时间复杂度是O(2^n)因为有大量重叠子问题被反复计算。DP的核心恰恰是记住子问题的解避免重复劳动——具体实现可以用迭代也可以用递归加记忆化也就是自顶向下DP。爬楼梯最适合先用迭代理解因为迭代的过程天然符合“从底向上一步步推”的思路。我见过不少新手在递归和迭代之间纠结半天其实完全没有必要两种方式能解决同一个问题底层思路一致你只要把迭代版本吃透递归版本自然水到渠成无非是加个缓存表的事。5.3 坑三空间优化一上来就做这个问题可能有点反直觉但真的是新手最容易犯的错。见过太多人一上来就写prev2、prev1版本AC之后觉得自己懂了DP。结果面试官换个问法维护一个数组pre里面存着每个位置的前缀和请问怎么高效计算区间和他立刻懵了——因为他在爬楼梯里没建过数组没有感受过“数组下标的物理含义”。我的建议是第一次做爬楼梯必须老老实实把dp数组完整写出来哪怕空间是O(n)。打印dp数组观察它的每一项怎么递推出来。当你对数据流有了实感再去做空间压缩此时滚动变量只是顺手的事。先学走再学跑在DP这里特别适用。5.4 坑四一题一法不会迁移做完爬楼梯很多人的下一步是刷更多同类型的简单题然后背下每道题的代码。这种做法最致命的不是记忆负担大而是当你遇到一道没见过的新题时没有任何可以依赖的思考框架。爬楼梯的思考框架可以怎么迁移举个例子假如题目变成“一个机器人在m×n的网格上从左上角走到右下角只能向右或向下”这就是LeetCode 62不同路径。它的状态定义是dp[i][j]表示从起点走到(i,j)的路径数转移方程是dp[i][j]dp[i-1][j]dp[i][j-1]——仔细看看这和爬楼梯的加法思想一模一样只不过从一维变成了二维。所以每做完一道题我都会强迫自己写一句“这题的核心套路是什么”然后在下一次做题时尝试套用。爬楼梯的核心套路就是站在当前状态上一步从哪里来把所有可能来源相加计数或取最优最优化。这个套路能解决大量DP入门题甚至中级题。5.5 做题节奏建议如果你完全零基础我推荐的做题顺序是70爬楼梯一维加法746最小花费爬楼梯一维取min62不同路径二维加法63不同路径II带障碍然后回头看198打家劫舍一维变体最后做322零钱兑换完全背包。这一串题目下来DP的几条主线基本都能摸到。每次做题都只用同一个流程定义状态、写转移方程、定边界、实现、优化空间、总结套路。刚开始会很慢但我保证刷到第五六道的时候你会发现自己已经能闭着眼睛说出“这题先定义dp、再找依赖关系”的完整链路。我个人在实际操作里的一个体会是DP入门阶段的瓶颈从来不是代码能力而是“把自然语言翻译成状态定义”的能力。爬楼梯这道题之所以经典就是因为它给了你一个最轻量的翻译练习——每爬一级台阶往前看一步两步结果就出来了。把这层窗户纸捅破之后动态规划的路会顺很多。