LC 0070.Climbing Stairs

题目描述

这是 LeetCode 上的 70. 爬楼梯 ，难度为简单。

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

解答

方法一：动态规划

最简单方法是遍历所有的可能，即每次上台阶都有两种可能，上一级台阶或者上两级台阶，那么对于台阶总数为 n 的问题来说，时间复杂度为 \(O(2^n)\) ，当 n 足够大的时候，显然是不可接受的，下面介绍一种动态规划求解的方案。

不了解动态规划的，可以先看看第 14 章 动态规划这个熟悉一下。我们用 \(f(x)\) 表示爬到第 x 级台阶的方案数量，于是到第 x 级台阶有两种可能，一种是从前一级台阶向上走一级台阶，还有一种是从前两级台阶一次走两个台阶，于是到第 x 级台阶的方案数就等于前一级台阶到当前台阶的方案数加上前两级台阶到当前台阶的方案数，即 \(f(x) = f(x - 1) + f(x - 2)\)。

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1, b = 2;
        for (int i = 3; i < n; ++i) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return a + b;
    }
}

为了不处理特殊的边界条件，我们引入第 0 级台阶，从第 0 级台阶到第 0 级台阶可以看作是只有一种方法，可以证明这样处理边界条件和之前的方案求出的结果是一样的。

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

• 时间复杂度：\(O(n)\)，循环执行 n 次，其中 n 为台阶的数量。

• 空间复杂度：\(O(1)\)，使用常数个变量作为辅助空间。

方法二：矩阵快速幂

@Source:解法来源

当 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\) 的求取。

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

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

\[ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_m \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \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) \] 于是就可以继续使用矩阵快速幂求解，当然不是所有的非齐次线性都可以转化为齐次线性，还是需要具体问题具体分析。

public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) { // 判断奇偶性，每次取余之后都要判断
                ret = multiply(ret, a); // 乘以当前的矩阵
            }
            n >>= 1; // 对2取余的操作
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) { // 二维矩阵乘法
        int[][] c = new int[2][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;
    }
}

• 时间复杂度：\(O(\log n)\)，和快速幂的时间复杂度一样。

• 空间复杂度：\(O(1)\)，只使用了常数个变量。

方法三：通项公式

@Source:解法来源

根据齐次线性递推公式的特点，根据递推方程 \(f(n) = f(n - 1) + f(n - 2)\) ，可以写出特征根方程 \(x^2 = x + 1\) 求得 \(x_1 = \frac{1 + \sqrt{5}}{2}\)，\(x_2 = \frac{1 - \sqrt{5}}{2}\)，设通解为 \(f(n) = c_1x_1^n + c_2x_2^n\)，代入初始条件 \(f(1) = 1\)，\(F(2) = 1\)，得到 \(c_1 = \frac{1}{\sqrt{5}}\)， \(c_2 = -\frac{1}{\sqrt{5}}\)，于是就有这个递推数列的通项公式： \[ f(n) = \frac{1}{\sqrt{5}}[(\frac{1 + \sqrt{5}}{2})^n - \frac{1 - \sqrt{5}}{2})^n] \] 接着就可以直接通过通项公式直接求第 \(n\) 项。

public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);
    }
}

• 时间复杂度：\(O()\)，取决于内部函数 pow 的时间复杂度。
• 空间复杂度：\(O()\)，取决于内部函数 pow 的空间复杂度。

每题一图