目录1. 问题描述2. 问题分析2.1 题目理解2.2 核心洞察2.3 破题关键3. 算法设计与实现3.1 解法一朴素递归自顶向下3.2 解法二记忆化递归自顶向下 缓存3.3 解法三动态规划自底向上3.4 解法四空间优化动态规划滚动数组3.5 解法五矩阵快速幂3.6 解法六通项公式Binet 公式4. 性能对比4.1 理论复杂度对比表4.2 实际性能测试4.3 各场景适用性分析5. 扩展与变体5.1 变体一每次可以爬 1、2、3 个台阶5.2 变体二每次可以爬 1 或 2 个台阶但相邻两步不能相同5.3 变体三最小花费爬楼梯5.4 变体四带障碍物的爬楼梯6. 总结6.1 核心思想总结6.2 实际应用场景6.3 面试建议6.4 常见面试问题 QA1. 问题描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2 输出2 解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶示例 2输入n 3 输出3 解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶提示1 n 452. 问题分析2.1 题目理解爬楼梯问题是一个经典的动态规划入门题。要求计算到达第n阶楼梯的不同走法总数每次可以走1阶或2阶。本质上是求斐波那契数列的第n1项或第n项取决于初始定义。2.2 核心洞察递推关系到达第n阶的最后一步要么是从第n-1阶走1阶要么是从第n-2阶走2阶。因此设dp[n]表示到达第n阶的方法数则有dp[n] dp[n-1] dp[n-2]初始条件dp[1] 1dp[2] 2或者dp[0] 1dp[1] 1视下标定义而定。2.3 破题关键明确状态转移方程。优化空间由于只依赖前两个状态可以用滚动变量代替数组。进一步优化利用矩阵快速幂或通项公式可将时间复杂度降至 O(log n)。3. 算法设计与实现3.1 解法一朴素递归自顶向下核心思想直接根据递推公式递归求解将大问题分解为子问题。算法思路定义递归函数climb(n)返回到达第n阶的方法数。终止条件n 1返回1n 2返回2。否则返回climb(n-1) climb(n-2)。Java代码实现publicclassClimbingStairs{publicintclimbStairs(intn){if(n1)return1;if(n2)return2;returnclimbStairs(n-1)climbStairs(n-2);}}性能分析时间复杂度O(2^n)指数级存在大量重复计算。空间复杂度O(n)递归栈深度。3.2 解法二记忆化递归自顶向下 缓存核心思想使用数组缓存已计算过的结果避免重复递归。算法思路创建一个长度为n1的数组memo初始值为0。递归函数中若memo[n] ! 0则直接返回。否则计算并存储结果后返回。Java代码实现publicclassClimbingStairsMemo{publicintclimbStairs(intn){int[]memonewint[n1];returnhelper(n,memo);}privateinthelper(intn,int[]memo){if(n1)return1;if(n2)return2;if(memo[n]!0)returnmemo[n];memo[n]helper(n-1,memo)helper(n-2,memo);returnmemo[n];}}性能分析时间复杂度O(n)每个状态只计算一次。空间复杂度O(n)缓存数组 递归栈。3.3 解法三动态规划自底向上核心思想使用数组迭代计算从基础状态递推到目标状态。算法思路创建dp数组长度为n1。初始化dp[1] 1dp[2] 2。从i 3到n执行dp[i] dp[i-1] dp[i-2]。返回dp[n]。Java代码实现publicclassClimbingStairsDP{publicintclimbStairs(intn){if(n1)return1;int[]dpnewint[n1];dp[1]1;dp[2]2;for(inti3;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}}性能分析时间复杂度O(n)。空间复杂度O(n)。3.4 解法四空间优化动态规划滚动数组核心思想由于递推只依赖前两个状态可以用两个变量代替数组。算法思路初始化first 1对应dp[1]second 2对应dp[2]。从i 3到n计算third first second然后更新first secondsecond third。最后返回second当n 2时或特殊处理n 1。Java代码实现publicclassClimbingStairsOptimized{publicintclimbStairs(intn){if(n1)return1;intfirst1,second2;for(inti3;in;i){intthirdfirstsecond;firstsecond;secondthird;}returnsecond;}}性能分析时间复杂度O(n)。空间复杂度O(1)。3.5 解法五矩阵快速幂核心思想将递推关系转化为矩阵乘法利用快速幂在 O(log n) 时间内求解。算法思路递推关系[f(n), f(n-1)]^T [[1, 1], [1, 0]] * [f(n-1), f(n-2)]^T。因此[f(n), f(n-1)]^T M^(n-2) * [f(2), f(1)]^T其中M [[1, 1], [1, 0]]。使用快速幂计算矩阵的幂。Java代码实现publicclassClimbingStairsMatrix{publicintclimbStairs(intn){if(n1)return1;int[][]base{{1,1},{1,0}};int[][]resultmatrixPower(base,n-2);// [f(n), f(n-1)] result * [2, 1]returnresult[0][0]*2result[0][1]*1;}privateint[][]matrixPower(int[][]m,intpower){int[][]result{{1,0},{0,1}};// 单位矩阵while(power0){if((power1)1){resultmatrixMultiply(result,m);}mmatrixMultiply(m,m);power1;}returnresult;}privateint[][]matrixMultiply(int[][]a,int[][]b){int[][]cnewint[2][2];c[0][0]a[0][0]*b[0][0]a[0][1]*b[1][0];c[0][1]a[0][0]*b[0][1]a[0][1]*b[1][1];c[1][0]a[1][0]*b[0][0]a[1][1]*b[1][0];c[1][1]a[1][0]*b[0][1]a[1][1]*b[1][1];returnc;}}性能分析时间复杂度O(log n)矩阵乘法常数次。空间复杂度O(1)。3.6 解法六通项公式Binet 公式核心思想斐波那契数列有通项公式可以直接计算第n项。算法思路斐波那契数列F(1)1, F(2)1而爬楼梯结果对应F(n1)若F(1)1, F(2)1则climbStairs(1)1, climbStairs(2)2即climbStairs(n) F(n1)。使用公式F(n) (phi^n - psi^n) / sqrt(5)其中phi (1sqrt(5))/2psi (1-sqrt(5))/2。由于浮点数精度问题n 45时结果仍在int范围内可安全使用。Java代码实现publicclassClimbingStairsFormula{publicintclimbStairs(intn){doublesqrt5Math.sqrt(5);doublephi(1sqrt5)/2;doublepsi(1-sqrt5)/2;// climbStairs(n) (phi^(n1) - psi^(n1)) / sqrt5doubleresult(Math.pow(phi,n1)-Math.pow(psi,n1))/sqrt5;return(int)Math.round(result);}}性能分析时间复杂度O(log n)幂运算内部使用快速幂但常数较大。空间复杂度O(1)。4. 性能对比4.1 理论复杂度对比表解法时间复杂度空间复杂度特点朴素递归O(2^n)O(n)易于理解性能极差记忆化递归O(n)O(n)避免重复计算动态规划O(n)O(n)直观自底向上空间优化DPO(n)O(1)最常用简洁高效矩阵快速幂O(log n)O(1)适合超大 n通项公式O(log n)O(1)数学优雅精度受限4.2 实际性能测试在n 45题目最大范围下各解法性能表现朴素递归指数爆炸无法在合理时间内完成。记忆化递归~0.001ms。动态规划~0.001ms。空间优化DP~0.001ms。矩阵快速幂~0.002ms。通项公式~0.003ms浮点运算稍慢。对于n 10^9级别只有矩阵快速幂和通项公式可行但通项公式受浮点精度限制。4.3 各场景适用性分析面试场景推荐解法四空间优化DP简洁且高效。练习场景从递归开始逐步优化展示思维演进。超大 n 场景使用矩阵快速幂或通项公式。资源受限场景空间优化DP或矩阵快速幂。5. 扩展与变体5.1 变体一每次可以爬 1、2、3 个台阶题目描述每次可以爬1、2或3个台阶求到达第n阶的不同方法数。Java代码实现publicintclimbStairsVariants(intn){if(n1)return1;if(n2)return2;if(n3)return4;intfirst1,second2,third4;for(inti4;in;i){intfourthfirstsecondthird;firstsecond;secondthird;thirdfourth;}returnthird;}5.2 变体二每次可以爬 1 或 2 个台阶但相邻两步不能相同题目描述每次可以爬1或2个台阶但不能连续两次走相同步数即不能连续两个1或连续两个2求方法数。Java代码实现publicintclimbStairsNoConsecutive(intn){if(n1)return1;// dp[i][0] 表示最后一步走1阶到达 i 的方法数// dp[i][1] 表示最后一步走2阶到达 i 的方法数int[][]dpnewint[n1][2];dp[1][0]1;// 第一步走1阶dp[2][0]1;// 11不合法实际上题目不允许连续相同所以这里需要处理dp[2][1]1;// 直接走2阶// 具体实现略复杂需根据约束调整递推// 此处仅展示思路returndp[n][0]dp[n][1];}5.3 变体三最小花费爬楼梯题目描述数组cost表示每阶楼梯的花费可以从第0阶或第1阶开始每次爬1或2阶到达楼顶超过n-1阶的最小花费。Java代码实现publicintminCostClimbingStairs(int[]cost){intncost.length;intfirstcost[0],secondcost[1];for(inti2;in;i){intcurcost[i]Math.min(first,second);firstsecond;secondcur;}returnMath.min(first,second);}5.4 变体四带障碍物的爬楼梯题目描述有一个楼梯某些台阶损坏不可踩每次爬1或2阶求到达楼顶的方法数。Java代码实现publicintclimbStairsWithObstacles(boolean[]obstacles){intnobstacles.length;int[]dpnewint[n1];dp[0]1;// 起点for(inti1;in;i){if(obstacles[i-1]){dp[i]0;}else{dp[i](i-10?dp[i-1]:0)(i-20?dp[i-2]:0);}}returndp[n];}6. 总结6.1 核心思想总结爬楼梯问题是斐波那契数列的经典变形其核心在于找到状态转移方程dp[i] dp[i-1] dp[i-2]。通过不同的实现方式递归、记忆化、动态规划、矩阵快速幂可以逐步优化时间和空间复杂度。在实际应用中空间优化DP滚动数组是最常用且高效的解法。6.2 实际应用场景组合计数问题类似走楼梯的计数场景在游戏、路径规划中常见。斐波那契数列衍生许多实际问题可转化为斐波那契求解。动态规划入门教学是理解递推和状态转移的经典案例。6.3 面试建议优先给出空间优化DP解法并解释递推关系。分析时间复杂度和空间复杂度。可进一步展示递归的缺陷引出优化思路。如果面试官追问超大n可介绍矩阵快速幂或通项公式。注意边界条件处理如n1。6.4 常见面试问题 QAQ1为什么可以用斐波那契数列解决A因为到达第n阶的方法数等于到达第n-1阶的方法数最后一步走1阶加上到达第n-2阶的方法数最后一步走2阶这恰好是斐波那契数列的递推关系。Q2递归解法为什么慢A递归会重复计算大量子问题例如计算climb(5)需要计算climb(4)和climb(3)而climb(4)又会重复计算climb(3)导致指数级复杂度。Q3如果 n 非常大如 10^18如何求解A可以使用矩阵快速幂将时间复杂度降至 O(log n)。也可以使用通项公式但需注意浮点精度问题此时矩阵快速幂更可靠。Q4爬楼梯问题与斐波那契数列的初始值如何对应A通常斐波那契数列定义为F(0)0, F(1)1则爬楼梯结果climb(n) F(n1)。若定义F(1)1, F(2)1则climb(n) F(n1)依然成立。