【LeetCode】70. 爬楼梯

1 问题

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

2 答案

自己写的，回溯算法，但是超过了最大递归深度，运行不了，提交时超出内存限制了

class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(n, path, res):
            if n >= 2:
                for i in range(1,3):
                    dfs(n-i, path + [i], res)
            elif n == 1:
                dfs(n-1, path + [1], res)
            elif n == 0:
                res.append(path)
            else:
                return
        res = []
        path = []
        dfs(n, path, res)
        return len(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

官方解，动态规划

• 状态定义： 设 $dp$ 为一维数组，其中 $dp[i]$ 的值代表斐波那契数列的第 $i$ 个数字。
• 转移方程： $dp[i+1]=dp[i]+dp[i-1]$，即对应数列定义 $f(n+1)=f(n)+f(n-1)$。
• 初始状态： $dp[0]=1$, $dp[1]=1$，即初始化前两个数字。
• 返回值： $dp[n]$ ，即斐波那契数列的第 $n$ 个数字。

本题可转化为 求斐波那契数列的第 $n$ 项，区别仅在于初始值不同：

• 台阶问题： $f(0)=1,f(1)=1,f(2)=2$。
• 斐波那契数列问题： $f(0)=0,f(1)=1,f(2)=1$。

https://leetcode.cn/problems/climbing-stairs/solutions/2361764/70-pa-lou-ti-dong-tai-gui-hua-qing-xi-tu-ruwa/

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]  # dp[n]
1
2
3
4
5
6
7

优化，$f(n)$只依赖于$f(n-1)$和$f(n-2)$，只需要两项就足够了

class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1   # dp[0] = dp[1] = 1
        for _ in range(2, n+1):
            a, b = b, a+b
        return b
1
2
3
4
5
6

https://leetcode.cn/problems/climbing-stairs/solutions/661232/zhi-xin-hua-shi-pa-lou-ti-zhi-cong-bao-l-lo1t/