问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

代码解析

java

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;  // 初始化三个变量
        for(int i = 1; i <= n; ++i) {
            p = q;     // p 向前移动一步
            q = r;     // q 向前移动一步  
            r = p + q; // r 更新为前两个值的和
        }
        return r;       // 返回结果
    }
}

动态规划思想

这实际上是一个斐波那契数列问题：

• 到达第1阶：1种方法 (1)
• 到达第2阶：2种方法 (1+1, 2)
• 到达第n阶：到达第(n-1)阶的方法数 + 到达第(n-2)阶的方法数

因为你可以从第(n-1)阶爬1步上来，或者从第(n-2)阶爬2步上来。

图文解释

变量含义：

• p：代表到达第(i-2)阶的方法数
• q：代表到达第(i-1)阶的方法数
• r：代表到达第i阶的方法数

逐步执行过程（以 n=5 为例）：

初始状态：

text

i=0: p=0, q=0, r=1
(这相当于基础状态，为计算做准备)

第1次循环 (i=1)：

text

p = q = 0     // p 记录前前一个值
q = r = 1     // q 记录前一个值
r = p + q = 0 + 1 = 1

状态：到达第1阶有1种方法

第2次循环 (i=2)：

text

p = q = 1     // p = 1 (i-2=0阶的方法数)
q = r = 1     // q = 1 (i-1=1阶的方法数)
r = p + q = 1 + 1 = 2

状态：到达第2阶有2种方法

第3次循环 (i=3)：

text

p = q = 1     // p = 1 (i-2=1阶的方法数)
q = r = 2     // q = 2 (i-1=2阶的方法数)
r = p + q = 1 + 2 = 3

状态：到达第3阶有3种方法

第4次循环 (i=4)：

text

p = q = 2     // p = 2 (i-2=2阶的方法数)
q = r = 3     // q = 3 (i-1=3阶的方法数)
r = p + q = 2 + 3 = 5

状态：到达第4阶有5种方法

第5次循环 (i=5)：

text

p = q = 3     // p = 3 (i-2=3阶的方法数)
q = r = 5     // q = 5 (i-1=4阶的方法数)
r = p + q = 3 + 5 = 8

状态：到达第5阶有8种方法

可视化表格：

台阶数	p (i-2)	q (i-1)	r (当前)	解释
初始化	0	0	1	基础状态
i=1	0	1	1	第1阶：1种方法
i=2	1	1	2	第2阶：2种方法
i=3	1	2	3	第3阶：3种方法
i=4	2	3	5	第4阶：5种方法
i=5	3	5	8	第5阶：8种方法

具体爬法示例（n=3）：

1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1

共3种方法，与计算结果一致。

算法优势

1. 时间复杂度：O(n)，只需要遍历一次
2. 空间复杂度：O(1)，只用了3个变量，常数空间
3. 效率高：避免了递归的重复计算问题