LeetCode81 - 爬楼梯 | 很多时候不懂事

📝 题目描述

题目链接：爬楼梯

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

💡 解题思路

方法一：动态规划

我们用 $f(x)$ 表示爬到第 $x$ 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

$f(x)=f(x−1)+f(x−2)$

它意味着爬到第 $x$ 级台阶的方案数是爬到第 $x−1$ 级台阶的方案数和爬到第 $x−2$ 级台阶的方案数的和。很好理解，因为每次只能爬 $1$ 级或 $2$ 级，所以 $f(x)$ 只能从 $f(x−1)$ 和 $f(x−2)$ 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 $0$ 级开始爬的，所以从第 $0$ 级爬到第 $0$ 级我们可以看作只有一种方案，即 $f(0)=1$ ；从第 $0$ 级到第 $1$ 级也只有一种方案，即爬一级， $f(1)=1$ 。这两个作为边界条件就可以继续向后推导出第 $n$ 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 $f(2)=2，f(3)=3，f(4)=5，……$ ，我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 $O(n)$ 的实现，但是由于这里的 $f(x)$ 只和 $f(x−1)$ 与 $f(x−2)$ 有关，所以我们可以用“滚动数组思想”把空间复杂度优化成 $O(1)$ 。

★方法二：矩阵快速幂

以上的方法适用于 $n$ 比较小的情况，在 $n$ 变大之后， $O(n)$ 的时间复杂度会让这个算法看起来有些捉襟见肘。我们可以用“矩阵快速幂”的方法来优化这个过程。

首先我们可以构建这样一个递推关系：

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} f(n)+f(n-1) \\ f(n) \end{bmatrix} = \begin{bmatrix} f(n+1) \\ f(n) \end{bmatrix}$

因此

$\begin{bmatrix} f(n+1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$

令

$M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

因此我们只要能快速计算矩阵 $M$ 的 $n$ 次幂，就可以得到 $f(n)$ 的值。如果直接求取 $M^n$ ，时间复杂度是 $O(n)$ 的，我们可以定义矩阵乘法，然后用快速幂算法来加速这里 $M^n$ 的求取。

如何想到使用矩阵快速幂？

如果一个问题可以转化为求解一个矩阵的 $n$ 次方的形式，那么可以用快速幂来加速计算
如果一个递归式形如 $f(n)={\textstyle \sum_{i-1}^{m}}a_if(n-1)$ ，即齐次线性递推式，我们就可以把数列的递推关系转化为矩阵的递推关系，即构造出一个矩阵的 $n$ 次方乘以一个列向量得到一个列向量，这个列向量中包含我们要求的 $f(n)$ 。一般情况下，形如 $f(n)={\textstyle \sum_{i-1}^{m}}a_if(n-1)$ 可以构造出这样的 $m×m$ 的矩阵：

$\begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_m \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}$

那么遇到非齐次线性递推我们是不是就束手无策了呢？其实未必。有些时候我们可以把非齐次线性递推转化为其次线性递推，比如这样一个递推：
$f(x)=(2x−6)c+f(x−1)+f(x−2)+f(x−3)$
我们可以做这样的变换：
$f(x)+xc=[f(x−1)+(x−1)c]+[f(x−2)+(x−2)c]+[f(x−3)+(x−3)c]$
令 $g(x)=f(x)+xc$ ，那么我们又得到了一个齐次线性递：
$g(x)=g(x−1)+g(x−2)+g(x−3)$
于是就可以使用矩阵快速幂求解了。当然并不是所有非齐次线性都可以化成齐次线性，我们还是要具体问题具体分析。

🔧 代码实现

1、动态规划

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1 || n == 2) return n;
        int dp_i_1 = 2, dp_i_2 = 1, dp_i = 0;
        for (int i = 3; i <= n; i++) {
            dp_i = dp_i_1 + dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
};

2、矩阵快速幂

class Solution {
public:
    vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
        vector<vector<long long>> c(2, vector<long long>(2));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
        vector<vector<long long>> ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = matrixPow(ret, n);
        return res[0][0];
    }
};

📊 复杂度分析

1、动态规划

时间复杂度： $O(n)$ ，循环执行 n 次，每次花费常数的时间代价。
空间复杂度： $O(1)$ ，只用了常数个变量作为辅助空间。

2、矩阵快速幂

时间复杂度： $O(logn)$ ，同快速幂。
空间复杂度： $O(1)$ 。

🎯 总结

核心思想：学会动态规划的模板写法。