LeetCode70-爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

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

提示

• 1 <= n <= 45

思路

先手动算出 n = 4 时的结果，将 n = 1…4 的结果列出来的时候，看着就像是 Fibonacci 数列，花了好长时间往这个数列上去理解，但是死活想不通。

最后去看了官方题解，就一句话“要上到 n 阶台阶只有两种方式：要么从 n - 1 阶台阶上跨 1 步上来，要么从 n - 2 阶台阶上跨 2 步上来，所以上 n 阶台阶的方式就是上 n - 1 阶台阶的方式加上 n - 2 阶台阶的方式“。

以为全部理解了，就写了递归求数列的代码拿去提交了。结果提交了好几次都在 44 这个测试用例上超时，所以递归是不行的，只能用递推的方式实现。

代码实现

递归很简单但是性能不佳，需采用递推的方式实现，也很简单。

class Solution:
    def climbStairs(self, n: int) -> int:
        first = 0
        second = 1
        for i in range(n):
            result = first + second
            first = second
            second = result
        return result