LeetCode 70. 爬楼梯（易）

斐波拉契数列，动态规划的典型问题。

题目

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

示例

示例 1： 

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

示例 2： 

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

  1. 1 阶 + 2 阶

  2. 2 阶 + 1 阶

考察知识点

动态规划

核心思想

类似第61题，递归方式的动态规划，计算从第一层到达每一层可能的N方法，一直叠加。
动态规划的状态转移公式为： dp[n] = dp[n-1] + dp[n-2]

Python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * n
        if n < 3:
            return n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

print("leet code accept!!!")
Input = [2, 3, 4]
Input1 = [2, 3]
Answer = [2, 3, 5]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.climbStairs(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
执行用时 :28 ms, 在所有 Python3 提交中击败了89.63%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.17%的用户

  • 一种简洁一点的写法，变长添加。
1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0:
            return 1
        if n <= 2:
            return n
        result=[1,2]
        for i in range(n-2):
            result.append(result[-2]+result[-1])
        return result[-1]

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
执行用时 :24 ms, 在所有 Python3 提交中击败了97.07%的用户 内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.17%的用户

  • 一种空间复杂度为\(O(1)\)的方法
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        yesterday = 2
        the_day_before_yesterday = 1
        for i in range(2, n):
            result = yesterday + the_day_before_yesterday
            the_day_before_yesterday = yesterday
            yesterday = result
        
        return result

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

参考连接

LeetCode官方题解