【刷穿 LeetCode】第 N 个泰波那契数 :「迭代」&「递归」&「矩阵快速幂」&「打表」

题目描述

这是 LeetCode 上的 1137. 第 N 个泰波那契数 ，难度为 简单。

Tag : 「动态规划」、「递归」、「递推」、「矩阵快速幂」、「打表」

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 nn，请返回第 nn 个泰波那契数 T_nTn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
复制代码

示例 2：

输入：n = 25
输出：1389537
复制代码

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^{31}231 - 1。

迭代实现动态规划

都直接给出状态转移方程了，其实就是道模拟题。

使用三个变量，从前往后算一遍即可。

代码：

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
}
复制代码

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

递归实现动态规划

也就是记忆化搜索，创建一个 cache 数组用于防止重复计算。

代码：

class Solution {
    int[] cache = new int[40];
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (cache[n] != 0) return cache[n];
        cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
        return cache[n];
    }
}
复制代码

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

矩阵快速幂

这还是一道「矩阵快速幂」的板子题。

首先你要对「快速幂」和「矩阵乘法」概念有所了解。

矩阵快速幂用于求解一般性问题：给定大小为 n * nn∗n 的矩阵 MM，求答案矩阵 M^kMk，并对答案矩阵中的每位元素对 PP 取模。

在上述两种解法中，当我们要求解 f[i]f[i] 时，需要将 f[0]f[0] 到 f[n - 1]f[n−1] 都算一遍，因此需要线性的复杂度。

对于此类的「数列递推」问题，我们可以使用「矩阵快速幂」来进行加速（比如要递归一个长度为 1e91e9 的数列，线性复杂度会被卡）。

使用矩阵快速幂，我们只需要 O(\log{n})O(logn) 的复杂度。

根据题目的递推关系（i >= 3i>=3）：

f(i) = f(i - 1) + f(i - 2) + f(i - 3)f(i)=f(i−1)+f(i−2)+f(i−3)

我们发现要求解 f(i)f(i)，其依赖的是 f(i - 1)f(i−1)、f(i - 2)f(i−2) 和 f(i - 3)f(i−3)。

我们可以将其存成一个列向量：

\begin{bmatrix} f(i - 1)\\ f(i - 2)\\ f(i - 3) \end{bmatrix}⎣⎢⎡f(i−1)f(i−2)f(i−3)⎦⎥⎤

当我们整理出依赖的列向量之后，不难发现，我们想求的 f(i)f(i) 所在的列向量是这样的：

\begin{bmatrix} f(i)\\ f(i - 1)\\ f(i - 2) \end{bmatrix}⎣⎢⎡f(i)f(i−1)f(i−2)⎦⎥⎤

利用题目给定的依赖关系，对目标矩阵元素进行展开：

\begin{bmatrix} f(i)\\ f(i - 1)\\ f(i - 2) \end{bmatrix} = \begin{bmatrix} f(i - 1) * 1 + f(i - 2) * 1 + f(i - 3) * 1\\ f(i - 1) * 1 + f(i - 2) * 0 + f(i - 3) * 0\\ f(i - 1) * 0 + f(i - 2) * 1 + f(i - 3) * 0 \end{bmatrix}

⎣⎢⎡f(i)f(i−1)f(i−2)⎦⎥⎤=⎣⎢⎡f(i−1)∗1+f(i−2)∗1+f(i−3)∗1f(i−1)∗1+f(i−2)∗0+f(i−3)∗0f(i−1)∗0+f(i−2)∗1+f(i−3)∗0⎦⎥⎤

那么根据矩阵乘法，即有：

\begin{bmatrix} f(i)\\ f(i - 1)\\ f(i - 2) \end{bmatrix} = \begin{bmatrix} 1 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \end{bmatrix} * \begin{bmatrix} f(i - 1)\\ f(i - 2)\\ f(i - 3) \end{bmatrix}⎣⎢⎡f(i)f(i−1)f(i−2)⎦⎥⎤=⎣⎢⎡110101100⎦⎥⎤∗⎣⎢⎡f(i−1)f(i−2)f(i−3)⎦⎥⎤

我们令

Mat = \begin{bmatrix} 1 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \end{bmatrix}Mat=⎣⎢⎡110101100⎦⎥⎤

然后发现，利用 MatMat 我们也能实现数列递推（公式太难敲了，随便列两项吧）：

Mat * \begin{bmatrix} f(i - 1)\\ f(i - 2)\\ f(i - 3) \end{bmatrix} = \begin{bmatrix} f(i)\\ f(i - 1)\\ f(i - 2) \end{bmatrix}Mat∗⎣⎢⎡f(i−1)f(i−2)f(i−3)⎦⎥⎤=⎣⎢⎡f(i)f(i−1)f(i−2)⎦⎥⎤

Mat * \begin{bmatrix} f(i )\\ f(i - 1)\\ f(i - 2) \end{bmatrix} = \begin{bmatrix} f(i + 1)\\ f(i)\\ f(i - 1) \end{bmatrix}Mat∗⎣⎢⎡f(i)f(i−1)f(i−2)⎦⎥⎤=⎣⎢⎡f(i+1)f(i)f(i−1)⎦⎥⎤

再根据矩阵运算的结合律，最终有：

\begin{bmatrix} f(n)\\ f(n - 1)\\ f(n - 2) \end{bmatrix} = Mat^{n - 2} * \begin{bmatrix} f(2)\\ f(1)\\ f(0) \end{bmatrix}⎣⎢⎡f(n)f(n−1)f(n−2)⎦⎥⎤=Matn−2∗⎣⎢⎡f(2)f(1)f(0)⎦⎥⎤

从而将问题转化为求解 Mat^{n - 2}Matn−2 ，这时候可以套用「矩阵快速幂」解决方案。

代码：

class Solution {
    int N = 3;
    int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
            }
        }
        return c;
    }
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[][] ans = new int[][]{
            {1,0,0},
            {0,1,0},
            {0,0,1}
        };
        int[][] mat = new int[][]{
            {1,1,1},
            {1,0,0},
            {0,1,0}
        };
        int k = n - 2;
        while (k != 0) {
            if ((k & 1) != 0) ans = mul(ans, mat);
            mat = mul(mat, mat);
            k >>= 1;
        }
        return ans[0][0] + ans[0][1];
    }
}
复制代码

• 时间复杂度：O(\log{n})O(logn)
• 空间复杂度：O(1)O(1)

打表

当然，我们也可以将数据范围内的所有答案进行打表预处理，然后在询问时直接查表返回。

但对这种题目进行打表带来的收益没有平常打表题的大，因为打表内容不是作为算法必须的一个环节，而直接是作为该询问的答案，但测试样例是不会相同的，即不会有两个测试数据都是 n = 37n=37。

这时候打表节省的计算量是不同测试数据之间的相同前缀计算量，例如 n = 36n=36 和 n = 37n=37，其 3535 之前的计算量只会被计算一次。

因此直接为「解法二」的 cache 添加 static 修饰其实是更好的方式：代码更短，同时也能起到同样的节省运算量的效果。

代码：

class Solution {
    static int[] cache = new int[40];
    static {
        cache[0] = 0;
        cache[1] = 1;
        cache[2] = 1;
        for (int i = 3; i < cache.length; i++) {
            cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
        }
    }
    public int tribonacci(int n) {
        return cache[n];
    }
}
复制代码

• 时间复杂度：将打表逻辑交给 OJOJ，复杂度为 O(C)O(C)，CC 固定为 4040。将打表逻辑放到本地进行，复杂度为 O(1)O(1)
• 空间复杂度：O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1035 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。