爬楼梯 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

入门视频

请看视频动态规划入门：从记忆化搜索到递推，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

一、启发思考：寻找子问题

假设 $n = 9$ 。

我们要解决的问题是从 $0$ 爬到 $9$ 有多少种不同的方法（或者说爬 $9$ 个台阶的方案数）。

分类讨论：

如果最后一步爬了 $1$ 个台阶，那么我们得先爬到 $8$ ，要解决的问题缩小成：从 $0$ 爬到 $8$ 有多少种不同的方法。
如果最后一步爬了 $2$ 个台阶，那么我们得先爬到 $7$ ，要解决的问题缩小成：从 $0$ 爬到 $7$ 有多少种不同的方法。

由于这两种情况都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。

注 1：从大往小思考，主要是为了方便把递归翻译成递推。从小往大思考也是可以的。
注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「枚举选哪个」。

二、递归怎么写：状态定义与状态转移方程

因为要解决的问题都是「从 $0$ 爬到 $i$ 」，所以定义 $dfs (i)$ 表示从 $0$ 爬到 $i$ 有多少种不同的方法（或者说爬 $i$ 个台阶的方案数）。

分类讨论：

如果最后一步爬了 $1$ 个台阶，那么我们得先爬到 $i - 1$ ，要解决的问题缩小成：从 $0$ 爬到 $i - 1$ 有多少种不同的方法。
如果最后一步爬了 $2$ 个台阶，那么我们得先爬到 $i - 2$ ，要解决的问题缩小成：从 $0$ 爬到 $i - 2$ 有多少种不同的方法。

由于这两种方法是互相独立的（爬的台阶个数不同），所以根据加法原理，从 $0$ 爬到 $i$ 的方法数等于这两种方法数之和，即

dfs (i) = dfs (i - 1) + dfs (i - 2)

递归边界： $dfs (0) = 1, dfs (1) = 1$ 。从 $0$ 爬到 $0$ 有一种方法，即原地不动。从 $0$ 爬到 $1$ 有一种方法，即爬 $1$ 个台阶。

递归入口： $dfs (n)$ ，也就是答案（爬 $n$ 个台阶的方案数）。

问：为什么 $0$ 到 $0$ 算一种方法？

答：也可以这样理解，如果 $dfs (0) = 0$ ，那么 $dfs (2) = dfs (1) + dfs (0) = 1$ ，这显然是错误的，因为有两种方法可以爬到 $2$ 。所以（倒推出） $dfs (0)$ 是 $1$ 。

Python 解法1C++ 解法1

python

# 会超时的递归代码
class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(i: int) -> int:
            if i <= 1:  # 递归边界
                return 1
            return dfs(i - 1) + dfs(i - 2)
        return dfs(n)

cpp

// C++ 版待补充

C++ 解法2

cpp

// 会超时的递归代码
class Solution {
    int dfs(int i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        return dfs(i - 1) + dfs(i - 2);
    }

public:
    int climbStairs(int n) {
        return dfs(n);
    }
};

复杂度分析

时间复杂度： $O (2^{n})$ 。搜索树可以近似为一棵二叉树，树高为 $O (n)$ ，所以节点个数为 $O (2^{n})$ ，遍历搜索树需要 $O (2^{n})$ 的时间。
空间复杂度： $O (n)$ 。递归需要 $O (n)$ 的栈空间。

三、递归 + 记录返回值 = 记忆化搜索

上面的做法太慢了，怎么优化呢？

注意到「先爬 $1$ 个台阶，再爬 $2$ 个台阶」和「先爬 $2$ 个台阶，再爬 $1$ 个台阶」，都相当于爬 $3$ 个台阶，都会从 $dfs (i)$ 递归到 $dfs (i - 3)$ 。

一叶知秋，整个递归中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $memo$ 数组中。
如果一个状态不是第一次遇到（ $memo$ 中保存的结果不等于 $memo$ 的初始值），那么可以直接返回 $memo$ 中保存的结果。

注意： $memo$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$ ，并且要记忆化的 $dfs (i)$ 也等于 $0$ ，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $- 1$ 。本题由于方案数均为正数，所以可以初始化成 $0$ 。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

Python 解法3C++ 解法3

python

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            if i <= 1:  # 递归边界
                return 1
            return dfs(i - 1) + dfs(i - 2)
        return dfs(n)

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
    vector<int> memo;

    int dfs(int i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        int& res = memo[i]; // 注意这里是引用
        if (res) { // 之前计算过
            return res;
        }
        return res = dfs(i - 1) + dfs(i - 2); // 记忆化
    }

public:
    int climbStairs(int n) {
        memo.resize(n + 1);
        return dfs(n);
    }
};

复杂度分析

时间复杂度： $O (n)$ 。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $O (n)$ ，单个状态的计算时间为 $O (1)$ ，所以动态规划的时间复杂度为 $O (n)$ 。
空间复杂度： $O (n)$ 。有多少个状态， $memo$ 数组的大小就是多少。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说， $f [i]$ 的定义和 $dfs (i)$ 的定义是一样的，都表示从 $0$ 爬到 $i$ 有多少种不同的方法（或者说爬 $i$ 个台阶的方案数）。

相应的递推式（状态转移方程）也和 $dfs$ 一样：

f [i] = f [i - 1] + f [i - 2]

相当于之前是用递归去计算每个状态，现在是枚举并计算每个状态。

初始值 $f [0] = 1, f [1] = 1$ ，翻译自递归边界 $dfs (0) = 1, dfs (1) = 1$ 。

答案为 $f [n]$ ，翻译自递归入口 $dfs (n)$ 。

Python 解法5C++ 解法5

python

class Solution:
    def climbStairs(self, n: int) -> int:
        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[n]

cpp

// C++ 版待补充

C++ 解法6

cpp

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
};

复杂度分析

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

五、空间优化

观察状态转移方程，发现一旦算出 $f [i]$ ，那么 $f [i - 2]$ 及其左边的状态就永远不会用到了。

这意味着每次循环，只需要知道「上一个状态」和「上上一个状态」的 $f$ 值是多少，分别记作 $f_{1}$ 和 $f_{0}$ 。它俩的初始值均为 $1$ ，对应着 $f [1]$ 和 $f [0]$ 。

每次循环，计算出新的状态 $newF = f_{1} + f_{0}$ ，那么对于下一轮循环来说：

「上上一个状态」就是 $f_{1}$ ，更新 $f_{0} = f_{1}$ 。
「上一个状态」就是 $newF$ ，更新 $f_{1} = newF$ 。

最后答案为 $f_{1}$ ，因为最后一轮循环算出的 $newF$ 赋给了 $f_{1}$ 。

Python 解法7C++ 解法7

python

class Solution:
    def climbStairs(self, n: int) -> int:
        f0 = f1 = 1
        for _ in range(2, n + 1):
            new_f = f1 + f0
            f0 = f1
            f1 = new_f
        return f1

cpp

// C++ 版待补充

Python 解法8C++ 解法8

python

class Solution:
    def climbStairs(self, n: int) -> int:
        f0 = f1 = 1
        for _ in range(2, n + 1):
            f0, f1 = f1, f1 + f0
        return f1

cpp

// C++ 版待补充

C++ 解法9

cpp

class Solution {
public:
    int climbStairs(int n) {
        int f0 = 1, f1 = 1;
        for (int i = 2; i <= n; i++) {
            int new_f = f1 + f0;
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

复杂度分析

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

六、矩阵快速幂优化

把状态转移方程用矩阵乘法表示，即

[\begin{matrix} f [i] \\ f [i - 1] \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} f [i - 1] \\ f [i - 2] \end{matrix}]

把上式中的三个矩阵分别记作 $F [i], M, F [i - 1]$ ，即

F [i] = M \times F [i - 1]

那么有

\begin{aligned} F [n] & = M \times F [n - 1] \\ = M \times M \times F [n - 2] \\ = M \times M \times M \times F [n - 3] \\ ⋮ \\ = M^{n} \times F [0] \end{aligned}

其中 $M^{n}$ 可以用快速幂计算，原理请看【图解】一张图秒懂快速幂。

初始值

F [0] = [\begin{matrix} f [0] \\ f [- 1] \end{matrix}] = [\begin{matrix} 1 \\ 0 \end{matrix}]

答案为 $f [n]$ ，即 $F [n]$ 的第一项。

Python 解法10C++ 解法10

python

# a @ b，其中 @ 是矩阵乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*b)]
            for row in a]

# a^n @ f0
def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
    res = f0
    while n:
        if n & 1:
            res = mul(a, res)
        a = mul(a, a)
        n >>= 1
    return res

class Solution:
    def climbStairs(self, n: int) -> int:
        m = [[1, 1], [1, 0]]
        f0 = [[1], [0]]
        fn = pow_mul(m, n, f0)
        return fn[0][0]

cpp

// C++ 版待补充

Python 解法11C++ 解法11

python

import numpy as np

class Solution:
    def climbStairs(self, n: int) -> int:
        m = np.array([[1, 1], [1, 0]], dtype=object)
        f0 = np.array([1, 0], dtype=object)
        fn = np.linalg.matrix_power(m, n) @ f0
        return fn[0]

cpp

// C++ 版待补充

C++ 解法12

cpp

using matrix = vector<vector<long long>>;

// 返回矩阵 a 和矩阵 b 相乘的结果
matrix mul(matrix& a, matrix& b) {
    int n = a.size(), m = b[0].size();
    matrix c = matrix(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < a[i].size(); k++) {
            if (a[i][k] == 0) {
                continue;
            }
            for (int j = 0; j < m; j++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

// a^n * f0
matrix pow_mul(matrix a, int n, matrix& f0) {
    matrix res = f0;
    while (n) {
        if (n & 1) {
            res = mul(a, res);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

class Solution {
public:
    int climbStairs(int n) {
        matrix m = {
            {1, 1},
            {1, 0},
        };
        matrix f0 = {{1}, {0}};
        matrix fn = pow_mul(m, n, f0);
        return fn[0][0];
    }
};

复杂度分析

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

思考题

如果每次可以爬 $1$ 或 $2$ 或 $3$ 个台阶呢？空间优化的写法要怎么做？
如果某些台阶不能爬呢？（输入一个数组表示不能爬的台阶编号）

欢迎在评论区发表你的思路。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

入门视频 ​

一、启发思考：寻找子问题 ​

二、递归怎么写：状态定义与状态转移方程 ​

复杂度分析 ​

三、递归 + 记录返回值 = 记忆化搜索 ​

复杂度分析 ​

四、1:1 翻译成递推 ​

复杂度分析 ​

五、空间优化 ​

复杂度分析 ​

六、矩阵快速幂优化 ​

复杂度分析 ​

思考题 ​

分类题单 ​

入门视频

一、启发思考：寻找子问题

二、递归怎么写：状态定义与状态转移方程

复杂度分析

三、递归 + 记录返回值 = 记忆化搜索

复杂度分析

四、1:1 翻译成递推

复杂度分析

五、空间优化

复杂度分析

六、矩阵快速幂优化

复杂度分析

思考题

分类题单