一、题目

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

二、示例

输入：

n = 2

输出：

2

三、解析

用f(x)表示爬到第x级台阶的方案数，由于只能一步或两步进行攀爬，因此可得：f(x) = f(x-1) +f(x-2)，即爬到第x级台阶的方案数是爬到第x-1级台阶和爬到第x-2级台阶的总和。
起始x设为0，令f(0) = 1，即爬到第0级台阶只有一种方案，由题易知，f(1) = 1，f(2) = 2， f(3) = 3，f(4) = 5 …将所有情况枚举出来，可知f(x)与第x（第一个记作0）个斐波那契数列相同，即转化为求斐波那契数列。

四、代码

python代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        p, q = 0, 0
        r = 1
        for i in range(n):
            p = q
            q = r
            r = p + q
        return r

运行结果：