🏗️ 爬楼梯

📝 题目描述

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

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

📋 代码模版

java

class Solution {
    public int climbStairs(int n) {

    }
}

typescript

function climbStairs(n: number): number {
    
}

💡 提示

1. $1\le n\le 45$

🚀 示例

🖊️ 题解

记忆化搜索

​ 我们可以先考虑最简单的情况。如果楼梯台阶只有一级，那么爬到楼顶的方法总数为1种，即仅爬1阶。如果楼梯台阶只有二级，那么爬到楼顶的方法总数为2种，分别为爬1阶 + 1阶、仅爬2阶。

​ 如果楼梯台阶超过了二级（n >= 3），那么爬到第n阶的方法总数计算可以分为以下两种情况。

1. 爬到第n - 1阶有多少种方法？
2. 爬到第n - 2阶有多少种方法？

​ 而爬到第n阶的方法总数就等于爬到i - 1阶的方法总数加上爬到i - 2阶的方法总数。因为如果想要爬到第n阶，无非就是在第n - 1阶再爬1阶，或在第n - 2阶再爬2阶。

​ 在上述过程中，原问题被拆分为两个子问题。通过仔细观察这两个子问题，我们发现它们与原问题相似，只是规模更小，并且当子问题的答案不明确时，我们仍然可以将其进一步分解为更小的子问题。

​ 因此，该题可以使用深度优先搜索dfs来解决。我们定义 $dfs(i)$ 为⭐️爬到第 $i$ 阶的方法总数⭐️，其中$1\le i\le n$。递归公式为 $dfs(i)=dfs(i-1)+dfs(i-2)$，递归边界为 $dfs(1)=1,dfs(2)=2$。

​ 综上所述，我们很容易写出以下代码。

java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

typescript

function climbStairs(n: number): number {
    if (n <= 2) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

​ 😭但经过实践，当输入的n增大到一定阈值时，以上代码的提交大概率会因为超时而无法通过。

​ 那么，导致以上代码运行效率低下的原因是什么呢？接下来，让我们来分析一下它的时间复杂度。假设n = 6，可以画出以下递归树。

​ 递归树为一颗二叉树。其中，每个节点都代表一个子问题的计算，节点总数为指数级别。因此，我们可以得出结论：随着n的增大，由于重复计算不断增加，子问题的个数也随之呈指数级增长。基于此，这个算法的时间复杂度为$O(2^n)$。

​ ⭐以上所述为多路递归的典型问题，即重复计算。为了应对这个问题，经典的解决方法是创建一个「备忘录」，在计算每个子问题之前先查找备忘录。如果备忘录中没有记录计算结果，就进行计算并将结果记录在备忘录中；反之，则直接获取记录的值并返回。

tip: 多路递归是指递归函数体中多次调用了自身。

​ 这种带备忘录的递归算法通常也被称为记忆化搜索，对应本题的算法代码如下。

java

class Solution {
    public int climbStairs(int n) {
        int[] memory = new int[n + 1];
        return dfs(n, memory);
    }

    private int dfs(int i, int[] memory) {
        if (i <= 2) {
            return i;
        }
        if (memory[i] != 0) {
            return memory[i];
        }
        return memory[i] = dfs(i - 1, memory) + dfs(i - 2, memory);
    }
}

typescript

function climbStairs(n: number): number {
    const memory: number[] = [];
    const dfs = (i: number): number => {
        if (i <= 2) {
            return i;
        }
        if (memory[i]) {
            return memory[i];
        }
        return memory[i] = dfs(i - 1) + dfs(i - 2);
    }
    return dfs(n);
}

​ 记忆化搜索是一种典型的空间换时间的思想，它是在一颗存在大量冗余的递归树上通过「剪枝」，保证了每个相同的节点只计算一次。因此，该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

动态规划

​ 根据以上dfs的解法，我们可以很轻松地将其翻译成动态规划dp解法，具体步骤如下。

1. 状态定义：设 $dp$ 为一维数组（逻辑上从索引1开始），其中 $dp[i]$ 代表⭐️爬到第i阶的方法总数⭐️，$1\le i\le n$。
2. 初始状态：根据边界条件，初始化 $dp$ 数组的前两项，即 $dp[1]=1,dp[2]=2$。
3. 状态转移方程：$dp[i]=dp[i-1]+dp[i-2]$，其中 $3\le i\le n$。
4. 返回值：$dp[n]$​，即爬到第n阶的方法总数。

java

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

typescript

function climbStairs(n: number): number {
    if (n <= 1) {
        return n;
    }
    const dp: number[] = [];
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

​ 以上算法需要一个很长的DP table（ $dp$ 数组）来存储所有的状态，但我们仔细观察状态转移方程 $dp[i]=dp[i-1]+dp[i-2]$，可以发现当前状态的计算只依赖于前两个状态。因此我们可以通过「滚动数组」的思想，利用若干变量替代 $dp$ 数组，在保持算法的时间复杂度不变的前提下，将空间复杂度从 $O(n)$ 优化至 $O(1)$。

​ 这种技巧通常也被称为状态压缩，对应本题的算法代码如下。

java

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        int pre = 1, cur = 2;
        for (int i = 3; i <= n; i++) {
            int sum = pre + cur;
            pre = cur;
            cur = sum;
        }
        return cur;
    }
}

typescript

function climbStairs(n: number): number {
    if (n <= 1) {
        return n;
    }
    let pre = 1, cur = 2;
    for (let i = 3; i <= n; i++) {
        const sum = pre + cur;
        pre = cur;
        cur = sum;
    }
    return cur;
}

💭 复杂度分析

​ 基于记忆化搜索的解决方案的复杂度分析如下。

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

​ 基于动态规划的最优（状态压缩）解决方案的复杂度分析如下。

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