LeetCode爬楼梯问题详解：从递归到递推的优化

LeetCode爬楼梯问题详解：从递归到递推的优化

引用

CSDN

1.

https://blog.csdn.net/2301_80269840/article/details/139017012

爬楼梯问题是LeetCode上一个经典的动态规划题目，主要考察递归、记忆化搜索和递推等算法思想。本文将从问题描述出发，详细讲解这三种解法，并分析它们的时间和空间复杂度。

题目

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

方法一：递归

def dfs(i:int) -> int:
    if i <= 1:
        return 1
    elif i < 0:
        return 0
    return dfs(i - 1) + dfs(i - 2)
return dfs(n)

提交的时候会发现，时间超限了，因为单纯的递归时间复杂度是指数级的，时间复杂度为o（2^n)
空间复杂度为o（n）的栈空间

方法二：记忆化搜索

Python用户直接使用cache解释器就可以了，在functools库中导入

from functools import cache

@cache
def dfs(i:int) -> int:
    if i <= 1:
        return 1
    elif i < 0:
        return 0
    return dfs(i - 1) + dfs(i - 2)
return dfs(n)

非Python用户可以建一个memo数组用来记录已访问的节点，这样更加省时间不用进行重复计算。

memo = [0] * (n + 1)
def dfs(i:int) -> int:
    if i <= 1:
        return 1
    elif i < 0:
        return 0
    if memo[i] != 0:
        return memo[i]
    memo[i] = dfs(i - 1) + dfs(i - 2)
    return memo[i]
return dfs(n)

时间复杂度：O(n)。由于每个状态只会计算一次，
空间复杂度：O(n)。有多少个状态，memo数组的大小就是多少。

方法三：翻译为递推

递归是自上而下返回上的过程，如果省去自上而下只要自下而上呢？
注意：递推和递归的状态转移方程也就是递推式是一样的，并且出口和入口也都是可翻译的，唯一要注意的是，递推需要初始值也就是底，而递归需要的是边界值
以下是翻译，一定要好好理解：
递归的边界：dfs(0) = 1, dfs(1) = 1 翻译为递推的 f[0]=1,f[1]=1
递归的入口：dfs(n)，翻译为递推的入口f[n]

代码如下：

f = [0] * (n + 1)
f[0] = f[1] = 1
for i in range(2,n + 1):
    f[i] = f[i - 1] + f[i - 2]
return f[-1]

由于f[i]只跟前两个值有关，所以可以进行空间优化，像斐波那契一样。

f0 = f1 = 1
for _ in range(2,n + 1):
    fnew = f0 + f1
    f0 = f1
    f1 = fnew
return f1

这两段代码的时间复杂度都是o（n），第一段的空间是o（n）第二段是o（1）