70. 爬楼梯

发表于 2026-01-04 分类于力扣阅读次数： Waline：本文字数： 387 阅读时长 ≈ 1 分钟

考点

线性DP

思路

一、问题描述

给定一个正整数 \(n\)，表示楼梯的总阶数。每次可以选择爬 1 阶 或 2 阶，问共有多少种不同的方法可以爬到第 \(n\) 阶。

二、状态定义

设 \[ f[i] \] 表示到达第 \(i\) 阶楼梯的不同走法数量。

三、初始条件

到达第 \(0\) 阶（地面）只有一种方式：什么都不做 \[ f[0] = 1 \]
其余状态初始为 \(0\)

四、状态转移方程

从任意第 \(i\) 阶出发：

走 1 阶 可以到达第 \(i+1\) 阶
走 2 阶 可以到达第 \(i+2\) 阶

因此有如下转移关系： \[ \begin{aligned} f[i+1] &+= f[i] \\ f[i+2] &+= f[i] \end{aligned} \] 这表示：

当前到达第 \(i\) 阶的所有方案，都会分别贡献给 \(i+1\) 和 \(i+2\)。

五、迭代过程说明

算法从第 \(0\) 阶开始，依次向上更新：

for (int i = 0; i < n; ++i) {
    f[i + 1] += f[i];
    f[i + 2] += f[i];
}

循环保证所有可行状态都会被统计
最终答案即为： \[ f[n] \]

六、AC代码

class Solution {
public:
    int climbStairs(int n) {
        int f[50] = {};
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            f[i + 1] += f[i];
            f[i + 2] += f[i];
        }
        return f[n];
    }
};

七、复杂度分析

时间复杂度： \[ O(n) \]
空间复杂度： \[ O(n) \]

八、与斐波那契数列的关系

该问题本质上满足以下递推式： \[ f[n] = f[n-1] + f[n-2] \] 因此它与斐波那契数列完全一致，只是初始条件不同： \[ \begin{cases} f[0] = 1 \\ f[1] = 1 \end{cases} \]

0%