题目描述

一个楼梯一共 $n$ 级，你每次可以上一级或两级台阶，问一共有多少种方法爬上楼顶。

注意：$n$ 是正整数。

样例

输入：2
输出：2
解释：一共有两种方式爬到楼顶：
1. 1级 + 1级
2. 2级

样例2

输入：3
输出：3
解释：一共有三种方式爬到楼顶：
1. 1级 + 1级 + 1级
2. 1级 + 2级
3. 2级 + 1级

算法

(递推) $O(n)$

定义数组 $f[i]$ 表示上 $i$ 级台阶的方案数，则枚举最后一步是上1级台阶，还是上2级台阶，所以有：
$f[i] = f[i-1] + f[i-2]$。

时间复杂度分析：递推状态数 $O(n)$，转移时间复杂度是 $O(1)$，所以总时间复杂度是 $O(n)$。

C++ 代码

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