Climbing Stairs

70. 爬楼梯

分析

典型的斐波那契数列问题。到达第 n 阶的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和状态转移方程：f(n) = f(n-1) + f(n-2)

初始条件：

f(0) = 1 ：到达第 1 阶的方法只有一种
f(1) = 1 ：到达第 1 阶的方法只有一种
f(2) = 2 ：到达第 2 阶的方法是两种 1 + 1

通过观察状态转移公式，问题可以转化为计算斐波那契数列的第 n 项
使用两个变量来存储状态值，优化空间复杂度：
- a ：表示到达前一阶的方法数
- b ：表示到达当前阶的方法数
迭代更新 a 和 b 的值，直到计算到第 n 阶

时间复杂度

循环执行 n - 1 次，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    int climbStairs(int n)
    {
        int a = 1, b = 1;   // 初始状态：f(0) = 1, f(1) = 1
        while ( -- n)       // 从第 2 阶开始计算
        {
            int c = a + b;  // 当前阶方法数等于前两阶之和
            a = b;          // 更新前一阶为当前阶
            b = c;          // 更新当前阶为下一阶
        }
        return b;           // 返回第 n 阶的方法数
    }
};