LeetCode 70. 爬楼梯是入门级动态规划经典题也是面试高频基础题。核心考点是理解“状态转移”逻辑看似简单却能帮我们快速建立动态规划思维。本文将先回顾题目核心再拆解一段爬楼梯TypeScript代码的逻辑、分析其优缺点随后给出多套优化方案及补充方法覆盖基础到进阶适合新手快速吃透这道题。一、题目回顾快速把握核心需求题目描述假设你正在爬楼梯需要 n 阶才能到达楼顶每次可以爬 1 或 2 个台阶求有多少种不同的爬楼方法核心规律解题关键后续所有方法均围绕此展开n11种方法直接爬1阶n22种方法11、直接爬2阶n≥3第n阶的方法数 第n-1阶方法数 第n-2阶方法数本质是斐波那契数列仅初始值不同二、现有代码拆解读懂逻辑找准问题先贴出待拆解代码我们逐行分析其实现思路、核心逻辑同时找出可优化的痛点functionclimbStairs(n:number):number{letcur0;letbef-1;for(leti0;in;i){constnext(cur0?0:(cur0?1:cur))(bef0?0:(bef0?1:bef));befcur;curnext;}returncur;};2.1 核心思路定位这段代码的核心思路是「迭代递推」—— 用两个变量cur、bef记录“当前状态”和“前一个状态”的方法数避免用数组存储所有状态从而将空间复杂度优化至O(1)这是其核心优点。这里的“状态”对应cur 表示当前迭代轮次对应的台阶数的方法数bef 表示上一轮前一个台阶数的方法数通过循环逐步递推到第n阶最终得到结果。2.2 逐行拆解逻辑变量初始化let cur 0; let bef -1;cur初始值为0用于记录“当前台阶数”的方法数bef初始值为-1用于记录“前一个台阶数”的方法数注初始值看似特殊bef-1、cur0是为了通过后续判断贴合爬楼梯的初始规律n1、n2的情况。循环执行for (let i 0; i n; i) { … }核心计算next 的取值逻辑最关键部分本质对应递推公式下一个方法数 当前方法数 前一个方法数对 cur 的判断cur 0 取0cur 0 取1否则取cur本身处理初始值0和负数的特殊情况对 bef 的判断和cur逻辑一致bef 0 取0bef 0 取1否则取bef本身举例理解n1时i0循环1次next (00?1:0) (-10?0:-1) 101此时cur更新为1最终返回1符合n1的正确结果。状态更新bef cur; cur next;每轮循环后将当前的cur当前方法数赋值给bef变为下一轮的“前一个方法数”将计算出的next下一个方法数赋值给cur变为下一轮的“当前方法数”返回结果循环n次后cur即为第n阶的方法数。2.3 代码优缺点分析找准优化方向优点值得肯定空间优化到位仅使用2个变量cur、bef空间复杂度为O(1)避免了用数组存储所有台阶方法数的额外开销无栈溢出风险采用迭代思路而非递归即使n较大如n45也不会出现递归栈溢出的问题时间复杂度为O(n)效率达标。缺点优化痛点逻辑冗余对cur和bef的判断cur0、cur0完全可以简化初始值的特殊情况可通过边界处理提前解决无需每轮循环都判断可读性差next的计算逻辑写在一行包含多个三元运算符不熟悉这段代码的人需要反复琢磨才能理解其意图初始值不直观bef-1、cur0的初始值不符合爬楼梯的实际规律台阶数的方法数不会是负数增加了理解成本。三、针对性优化方案3种写法逐步简化优化核心保留原代码“迭代递推O(1)空间”的优点简化冗余判断、优化初始值、提升可读性同时保证代码正确性。以下3种优化写法均保持O(n)时间复杂度、O(1)空间复杂度适配不同理解习惯。优化写法1简化初始值推荐面试首选结合爬楼梯的初始规律n1→1种、n2→2种直接初始化前两个状态去掉所有冗余判断可读性拉满也是面试中最稳妥的写法。functionclimbStairs(n:number):number{// 边界处理提前解决n1、n2的情况无需循环if(n2)returnn;// a 第n-2阶方法数b 第n-1阶方法数初始贴合n1、n2leta1,b2;// 从n3开始递推直到n阶for(leti3;in;i){consttempab;// 当前n阶方法数 前两阶之和递推核心ab;// 更新n-2阶为原来的n-1阶btemp;// 更新n-1阶为当前n阶}returnb;// 循环结束后b即为第n阶方法数};优势逻辑简洁、初始值直观无任何冗余判断新手也能一眼看懂提交LeetCode可直接通过适配题目所有测试用例。优化写法2兼容原代码变量逻辑简化判断如果想保留原代码的cur、bef变量命名习惯仅简化next的计算逻辑去掉不必要的三元判断贴合原思路的同时提升可读性。functionclimbStairs(n:number):number{// 边界处理提前解决n1的特殊情况if(n1)return1;// 初始值优化贴合递推规律去掉负数无需额外判断letcur1;// 对应n1时的方法数letbef1;// 辅助变量适配递推逻辑// 从n2开始递推n1已提前处理for(leti2;in;i){constnextcurbef;// 直接用递推公式无需判断befcur;curnext;}returncur;};优化写法3极简版适合追求代码简洁度在优化写法1的基础上进一步简化代码去掉临时变量temp适合熟悉递推逻辑后使用。functionclimbStairs(n:number):number{leta1,b1;for(leti2;in;i){[a,b][b,ab];// 解构赋值简化状态更新}returnb;};注这里初始值a1、b1是因为循环从i2开始递推到n时b会自动对应第n阶的方法数和题目规律完全匹配n2时循环1次b112正确。四、补充方法覆盖基础到进阶适配不同场景除了上述迭代优化写法以下补充2种常用方法分别适配“理解递归思想”和“处理极大n”的场景帮你全面掌握这道题的解题思路。补充方法1递归记忆化解决纯递归超时问题纯递归思路简单但会出现大量重复计算时间复杂度O(2ⁿ)当n≥30时就会超时。通过“记忆化”存储已计算过的结果可将时间复杂度优化至O(n)空间复杂度O(n)适合理解递归思想和记忆化优化的核心。functionclimbStairs(n:number):number{// 用数组存储已计算的结果避免重复计算记忆化核心constmemonewArray(n1).fill(-1);// 递归辅助函数constdfs(i:number):number{// 边界条件i0地面、i11阶均只有1种方法if(i0||i1)return1;// 若已计算过直接返回结果无需重复递归if(memo[i]!-1)returnmemo[i];// 递推公式第i阶方法数 第i-1阶 第i-2阶memo[i]dfs(i-1)dfs(i-2);returnmemo[i];};returndfs(n);};优势思路直观完美贴合“第n阶第n-1阶第n-2阶”的核心规律适合新手理解递归与记忆化的结合缺点空间复杂度高于迭代法需额外存储记忆数组。补充方法2矩阵快速幂优化至O(logn)时间复杂度当n极大如n10⁶时O(n)的迭代法仍有优化空间矩阵快速幂可将时间复杂度降至O(logn)是进阶优化方案适合面试中体现代码功底核心是利用矩阵乘法简化递推过程。functionclimbStairs(n:number):number{// 定义矩阵乘法两个2x2矩阵相乘constmultiply(a:number[][],b:number[][]):number[][]{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]]];};// 定义矩阵快速幂矩阵a的k次方分治思想降低时间复杂度constmatrixPower(a:number[][],k:number):number[][]{// 初始为单位矩阵矩阵乘法的 identity 元素类似乘法中的1letres[[1,0],[0,1]];while(k0){// 若k为奇数先乘一次当前矩阵if(k%21)resmultiply(res,a);// 矩阵自乘k减半分治核心amultiply(a,a);kMath.floor(k/2);}returnres;};// 核心爬楼梯递推可转化为矩阵幂运算[[f(n1),f(n)],[f(n),f(n-1)]] [[1,1],[1,0]]^nif(n2)returnn;constmatrix[[1,1],[1,0]];constpowerMatrixmatrixPower(matrix,n-1);// f(n) powerMatrix[0][0]结合矩阵递推规律returnpowerMatrix[0][0];};优势时间复杂度O(logn)适合极大n的场景缺点逻辑相对复杂需掌握矩阵乘法和快速幂的分治思想日常开发和基础面试中使用较少适合进阶学习。五、总结解题核心与方法选择解题核心爬楼梯问题的本质是斐波那契数列的应用核心递推公式始终是「第n阶方法数 第n-1阶 第n-2阶」所有方法均围绕此公式展开区别仅在于实现方式和效率。方法选择建议基础面试/日常练习优先选择「优化写法1」兼顾可读性和规范性最容易被面试官认可追求代码简洁选择「优化写法3」用解构赋值简化状态更新代码更简洁理解递归思想选择「递归记忆化」直观贴合递推逻辑适合新手入门进阶提升/处理极大n选择「矩阵快速幂」体现代码功底应对极端场景。优化技巧无论哪种方法优化的关键都是「减少冗余计算、优化空间开销」—— 迭代法通过变量替代数组优化空间记忆化通过存储结果减少重复计算矩阵快速幂通过分治思想降低时间复杂度。