题目描述

[EN | CN]

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

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

注意:给定 n 是一个正整数。

示例 1:

1
2
3
4
5
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

1
2
3
4
5
6
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法 1:DP

经典动规题,每一个台阶的走法,等于上一级台阶的走法 + 上上级台阶的走法。

假设需要爬的楼梯阶为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

        a, b = 1, 2
        while n > 2:
            a, b = b, a + b
            n -= 1

        return b
  • 执行用时:36 ms,在所有 Python3 提交中击败了 84.39% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 20.59% 的用户。