爬楼梯——DP入门模型：斐波那契、矩阵快速幂、通项公式三种解法
爬楼梯——DP入门模型：斐波那契、矩阵快速幂、通项公式三种解法
适读人群：Java后端工程师、准备面试的同学 | 阅读时长：约18分钟 | 难度：Easy（但深度不易）
开篇故事
记得我第一次参加阿里的技术面试，大概是2012年的事了。彼时我已经有五六年开发经验，自我感觉还不错。面试官抛出一道题："爬楼梯，每次可以跨1步或2步，n级台阶有多少种走法？"
我心想，这不就是个递归嘛，刷刷几行写完了。面试官扫了一眼，说："好，时间复杂度呢？"我回答O(2^n)。他点点头，"能优化吗？"
我顿了一下，加了个备忘录，说O(n)了。他又问："n特别大，比如10^18，怎么办？"
这一问就把我干沉默了。后来才知道，这道题从Easy一路可以挖到矩阵快速幂，时间复杂度O(log n)。而那次面试我最终被问得哑口无言，印象极为深刻。
所谓DP入门题，并不代表只有一种解法。恰恰相反，爬楼梯这道题就像是一块试金石，能考察你对递推关系、状态压缩、数学本质理解得有多深。从记忆化搜索，到迭代DP，到矩阵快速幂，到黄金比例通项公式，每一层都是一扇新的门。
这篇文章，我打算把这三扇门都推开，让你看清楚里面究竟是什么。
一、题目解析
题号：LeetCode 70. Climbing Stairs
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
示例：
- 输入：n = 2，输出：2（1+1 或 2）
- 输入：n = 3，输出：3（1+1+1 或 1+2 或 2+1）
数据范围：1 ≤ n ≤ 45
核心考点：
- 线性递推关系（斐波那契数列）
- 状态定义与转移
- 空间优化
- 矩阵快速幂（进阶）
- 数学通项公式（进阶）
乍看是Easy，实际上考点极深。面试中一道"爬楼梯"往往能把候选人从会做分层到能优化、能扩展、能数学分析。
二、DP思路推导
2.1 状态定义的来龙去脉
做DP题，状态定义是核心。很多人上来就背答案，根本不知道为什么这样定义，换个题就不会了。
我们来想：站在第 n 级台阶上，你是从哪里来的？只有两种可能：
- 从第 n-1 级台阶跨了1步上来
- 从第 n-2 级台阶跨了2步上来
这两种情况是互斥且完备的——没有第三种可能（因为每次只能跨1步或2步）。
所以，到达第 n 级的方案数 = 到达第 n-1 级的方案数 + 到达第 n-2 级的方案数。
这就给了我们状态定义的自然出发点：
定义 dp[i] = 爬到第 i 级台阶的方案总数
为什么不定义"从第 i 级出发"？因为我们求的是"到达"，用"到达"定义语义更清晰，边界也更好处理。
2.2 状态转移方程推导
由上面的分析：
dp[i] = dp[i-1] + dp[i-2]这个方程怎么来的？我再强调一遍推导过程：
- 要到达第 i 级，最后一步要么是从 i-1 跨1步，要么是从 i-2 跨2步
- 从 i-1 跨1步到达 i 的方案数，就等于"到达 i-1 的方案数"（每种到达 i-1 的方案，加一步跨1阶就到 i）
- 从 i-2 跨2步到达 i 的方案数，就等于"到达 i-2 的方案数"（每种到达 i-2 的方案，加一步跨2阶就到 i）
- 两者相加，就是总方案数
这是"最后一步分析法"，是绝大多数DP状态转移推导的核心技巧。记住它。
2.3 边界条件分析
边界条件是DP最容易出错的地方。
dp[1] = 1：只有一种方法（跨1步）dp[2] = 2：两种方法（1+1 或 2）
有人喜欢从 dp[0] 开始定义：dp[0] = 1（站在地面，0种台阶，只有"不动"这一种状态）。这在数学上自洽，但初学时容易混淆，我建议先从 dp[1] 和 dp[2] 直接初始化，思路更清晰。
2.4 与斐波那契的关系
细心的读者会发现：dp[n] = dp[n-1] + dp[n-2]，这不就是斐波那契数列吗？
没错！爬楼梯的本质就是斐波那契数列，只不过初始值不同：
- 斐波那契：F(1)=1, F(2)=1, F(3)=2, F(4)=3...
- 爬楼梯：dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5...
爬楼梯的 dp[n] = F(n+1)，即斐波那契数列的第 n+1 项。
理解这个等价关系很重要，因为斐波那契数列有大量数学性质可以利用，矩阵快速幂和通项公式都是基于此展开的。
三、解法一：基础DP（迭代版）
完整思路
从 dp[1] 和 dp[2] 出发，逐步递推到 dp[n]。
public class ClimbingStairs {
/**
* 解法一：标准DP（数组版）
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
public int climbStairs(int n) {
if (n <= 2) return n;
// dp[i] 表示爬到第i级台阶的方案数
int[] dp = new int[n + 1];
// 边界初始化
dp[1] = 1; // 只有一种方法：跨1步
dp[2] = 2; // 两种方法：1+1 或 2
// 状态转移
for (int i = 3; i <= n; i++) {
// 最后一步从i-1跨1步，或从i-2跨2步
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}状态转移示意（Mermaid表格）：
| i | dp[i] | 推导来源 |
|----|-----------------|---------------------------|
| 1 | 1 | 边界初始化 |
| 2 | 2 | 边界初始化 |
| 3 | 3 = dp[2]+dp[1] | = 2 + 1 |
| 4 | 5 = dp[3]+dp[2] | = 3 + 2 |
| 5 | 8 = dp[4]+dp[3] | = 5 + 3 |
| n | dp[n-1]+dp[n-2] | 一般情况 |状态转移图（Mermaid）：
复杂度分析：
- 时间复杂度：O(n)，一次线性扫描
- 空间复杂度：O(n)，需要 n+1 大小的数组
对于 n ≤ 45 的数据范围，这个解法完全够用。
四、解法二：空间优化（滚动数组）
观察状态转移方程 dp[i] = dp[i-1] + dp[i-2]，每次计算只依赖前两个值，根本不需要存储整个数组。
用两个变量滚动更新即可。
/**
* 解法二：空间优化版（滚动变量）
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
public int climbStairsOptimized(int n) {
if (n <= 2) return n;
// prev2 对应 dp[i-2]，prev1 对应 dp[i-1]
int prev2 = 1; // dp[1]
int prev1 = 2; // dp[2]
int curr = 0;
for (int i = 3; i <= n; i++) {
curr = prev1 + prev2; // dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1; // 向前滚动
prev1 = curr;
}
return prev1;
}滚动过程示意：
空间复杂度从 O(n) 降到了 O(1)，这是DP空间优化最常用的技巧：当转移只依赖有限个历史状态时，滚动变量替代数组。
五、解法三：矩阵快速幂与通项公式
5.1 为什么需要更快的解法？
n ≤ 45 时，O(n) 已经足够。但如果 n 可以达到 10^18 呢？这时候 O(n) 的线性遍历根本跑不完，我们需要 O(log n) 的解法。
这道题就是这道题，但面试中经常以此为基础变体：求斐波那契数列第 n 项模 10^9+7，n ≤ 10^18。
5.2 矩阵快速幂
斐波那契数列有一个经典的矩阵表示：
[F(n+1)] [1 1]^n [1]
[F(n) ] = [1 0] × [0]爬楼梯的递推关系与斐波那契等价，所以：
[dp[n+1]] [1 1]^(n-1) [dp[2]] [1 1]^(n-1) [2]
[dp[n] ] = [1 0] × [dp[1]] = [1 0] × [1]通过矩阵快速幂，可以在 O(log n) 内计算矩阵的幂次。
/**
* 解法三：矩阵快速幂
* 时间复杂度：O(log n)
* 空间复杂度：O(1)
*/
public int climbStairsMatrix(int n) {
if (n <= 2) return n;
// 初始矩阵 [[1,1],[1,0]]
long[][] base = {{1, 1}, {1, 0}};
// 计算 base^(n-1)
long[][] result = matrixPow(base, n - 1);
// result × [2, 1]^T 的第一行第一列即为答案
// dp[n] = result[0][0] * dp[2] + result[0][1] * dp[1]
return (int)(result[0][0] * 2 + result[0][1] * 1);
}
/**
* 矩阵快速幂：计算矩阵 m 的 p 次方
*/
private long[][] matrixPow(long[][] m, int p) {
// 初始化为单位矩阵
long[][] result = {{1, 0}, {0, 1}};
while (p > 0) {
if ((p & 1) == 1) {
result = matrixMultiply(result, m);
}
m = matrixMultiply(m, m);
p >>= 1;
}
return result;
}
/**
* 2x2 矩阵乘法
*/
private long[][] matrixMultiply(long[][] a, long[][] b) {
int n = a.length;
long[][] c = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}快速幂原理：
将幂次 p 表示为二进制，利用 m^p = m^(p/2) × m^(p/2)（p为偶数）或 m^p = m × m^(p-1)（p为奇数）递归折半，每次计算只需要矩阵乘法，总计 O(log n) 次乘法。
p=6 = 110(二进制)
m^6 = m^4 × m^2
m^4 = (m^2)^2
m^2 = m × m5.3 数学通项公式（黄金比例）
斐波那契数列有封闭形式的通项公式，由 Binet 公式给出：
F(n) = (φ^n - ψ^n) / √5
其中 φ = (1 + √5) / 2 ≈ 1.618（黄金比例）
ψ = (1 - √5) / 2 ≈ -0.618爬楼梯 dp[n] = F(n+1)，所以：
dp[n] = round((φ^(n+1)) / √5)当 n 足够大时，ψ^(n+1)/√5 趋近于0，可以直接用四舍五入得到整数结果。
/**
* 解法四：数学通项公式
* 时间复杂度：O(1)（不考虑浮点幂运算）
* 空间复杂度：O(1)
* 注意：浮点精度问题，大n时不推荐
*/
public int climbStairsMath(int n) {
double sqrt5 = Math.sqrt(5);
double phi = (1 + sqrt5) / 2; // 黄金比例 φ
// dp[n] = F(n+1)，Binet公式
return (int) Math.round(Math.pow(phi, n + 1) / sqrt5);
}注意：浮点公式在 n 较大时会有精度误差，实际工程中不推荐使用。矩阵快速幂更可靠。
六、举一反三
同类DP题
LeetCode 746. 使用最小花费爬楼梯：在爬楼梯基础上加了每步的代价，dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
LeetCode 509. 斐波那契数：直接求斐波那契，是本题的纯粹形式
LeetCode 1137. 第N个泰波那契数：三阶线性递推，dp[i] = dp[i-1]+dp[i-2]+dp[i-3]，矩阵快速幂变为3×3
LeetCode 91. 解码方法：也是线性DP，但状态转移更复杂，依赖当前数字是否有效
通用解题框架
线性DP（一维）的通用框架：
1. 状态定义：dp[i] 表示"到达/处理到位置i时"的某种最优/计数结果
2. 状态转移：从"最后一步"倒推，dp[i] 由哪些状态转移而来
3. 边界初始化：i=0或i=1时的直接答案
4. 遍历顺序：通常从小到大（确保转移时所需的历史状态已经计算）
5. 空间优化：如果转移只用到有限历史，用滚动变量替代数组七、踩坑实录
坑一：忘记特判 n=1 的情况
空间优化版里，如果直接返回 prev1，要确保 n=1 时的边界正确。我当年就写过这样的bug：n=1时，循环根本不执行，prev1=2，直接返回2而不是1。一定要在最开始加 if (n <= 2) return n;。
坑二：int溢出
爬楼梯 n ≤ 45，dp[45] = 1134903170，还在 int 范围内。但如果是斐波那契的变体或者有模运算要求，必须用 long。矩阵快速幂里我直接用了 long[][]，就是为了防止这个坑。面试时很多人用 int[][]，一碰到取模题就出错。
坑三：矩阵乘法写错
矩阵快速幂最容易犯的错误是矩阵乘法实现写错。标准的矩阵乘法 C = A × B：
C[i][j] = Σ A[i][k] * B[k][j]，k从0到n-1有人把下标写成 A[i][k] * B[j][k]，结果完全不对。另一个坑是初始化结果矩阵时忘记清零——Java int数组默认是0，但如果复用了之前的数组就出事了。我在上面的代码里每次都 new 一个新数组，避免这个问题。
坑四：通项公式的浮点精度
数学公式看起来优雅，但在 n 较大时（比如 n=44, n=45），Math.pow 的浮点误差会导致四舍五入结果差1。我在实际测试中发现 n=44 时就可能出现精度问题。这个方法在面试中提一下即可，绝对不要直接用于生产。
坑五：区分斐波那契下标
爬楼梯的答案是斐波那契的第 n+1 项（如果从 F(1)=1, F(2)=1 开始数）。很多同学搞混这个对应关系，导致矩阵快速幂写完之后返回值差一项。建议先用小样本（n=3,4,5）验证一下对应关系。
八、总结
爬楼梯是DP的教科书级入门题，但它的深度远超表面：
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基础DP（数组） | O(n) | O(n) | 学习理解 |
| 滚动变量优化 | O(n) | O(1) | 通常够用 |
| 矩阵快速幂 | O(log n) | O(1) | n极大时 |
| 数学通项公式 | O(1) | O(1) | 学习了解，不推荐实用 |
从这道题出发，能延伸出整个斐波那契族的DP问题，以及矩阵快速幂在线性递推上的通用应用。
核心记忆点：
- "最后一步分析法"是推导转移方程的核心
- 只依赖有限历史状态的DP，可以用滚动变量把空间压到O(1)
- 矩阵快速幂是线性递推的通用加速手段，时间O(log n)
DP这条路，就从爬楼梯开始，一步一个脚印。