#70
简单
中频
动态规划爬楼梯
这是一道围绕算法展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
算法
题目分析
这道题表面上是在处理「爬楼梯」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 算法 这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：到第
i 级台阶的方法数，只可能来自第 i-1 级和第 i-2 级。推荐代码
推荐解法：动态规划
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 到第
i 级台阶的方法数，只可能来自第 i-1 级和第 i-2 级。class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int prev2 = 1;
int prev1 = 2;
for (int step = 3; step <= n; step++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用一维动态规划，因为当前位置的方法数只依赖前两个位置。
核心过程
- 定义
f(i)为到达第i级台阶的方法数。 - 转移方程是
f(i) = f(i - 1) + f(i - 2)。 - 初始化
f(1)=1、f(2)=2，然后从 3 递推到n。 - 因为只依赖前两项，所以可以用滚动变量把空间压到
O(1)。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最关键的是先把“当前状态来自前两步”说清楚。
核心思路
这题本质是一个一维递推问题。每一步只能走 1 级或 2 级，所以当前答案等于前两项之和，和斐波那契数列同构。
步骤讲解
1
先写清状态转移
设 f(i) 表示爬到第 i 级台阶的方法数。
为什么这样做：问题问的是“有多少种走法”，天然适合用 DP 计数。
对应代码提示：f(i) = f(i - 1) + f(i - 2)
2
初始化前两项
第 1 级只有 1 种走法，第 2 级有 2 种走法。
为什么这样做：后续所有状态都依赖这两个基础值。
对应代码提示：int prev2 = 1, prev1 = 2;
3
滚动更新到第 n 级
从小到大迭代，用两个变量保存最近两项即可。
为什么这样做：状态只依赖前两项，没必要开整张数组。
对应代码提示：int current = prev1 + prev2;
易错点
把 n=1 和 n=2 漏掉
这两个边界值不单独处理，循环很容易越界或返回错误答案。
正确理解：进入递推前先处理
n <= 2。开数组但下标定义混乱
有的人把 dp[0] 当 0，有的人当 1，最后转移式对不上。
正确理解：明确状态语义，保持一套下标定义写到底。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比直接递归少了大量重复计算。
适用判断：当状态只依赖固定个数的前序状态时，可以直接做滚动优化。
额外提醒
- 它和斐波那契数列同构，但面试时最好从状态转移推出来。