刷题记录 动态规划-3: 70. 爬楼梯

题目：70. 爬楼梯

难度：简单

假设你正在爬楼梯。需要 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

一、模式识别：动态规划

本题看似相比于斐波那契数列稍微复杂一点，但稍微分析一下就会发现一毛一样

五部曲：

1.动规数组意义：爬n台阶的方法个数

2.递推公式：和斐波那契数列一毛一样，解释：

当你需要爬n阶楼梯时，你有两个选择：

①爬1阶，再爬n - 1阶

②爬2阶，再爬n - 2阶

所以爬n阶的方法个数就是：爬n - 1阶的个数 + 爬n - 2阶的个数

即F(n) = F(n - 1) + F(n - 2)

3.初始化：斐波那契数列略有不同，F(0) 不存在，F(1) = 1，F(2) = 2；或者假定F(0) = 1

4.遍历顺序：本题常规，根据递推公式可知是从前往后

5.举例：较简单，这里省略

二、代码实现

这几种实现方式背后的代码逻辑相同，但各有优劣

1.缓存从0到n的F

该方法可读性较强，耗时低，但占空间较高

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [1] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

• 时间复杂度：O(n)
• 空间复杂度：O(n)

耗时：0ms

2.只缓存两个F

该方法可读性较弱，但耗时和占空间都较低

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [1] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

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

耗时：0ms

3.递归

注意：和斐波那契数列不同，本方法在本题中会超时

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)

• 时间复杂度：O(2^n)
• 空间复杂度：O(n)

耗时：超时