LC 1137. 第 N 个泰波那契数

题目描述

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

泰波那契序列 $T_{n}$ 定义如下：

$T{0} = 0$, $T{1} = 1$, $T{2} = 1$, 且在 $n >= 0$ 的条件下 $T{n+3} = T{n} + T{n+1} + T_{n+2}$

给你整数 $n$，请返回第 $n$ 个泰波那契数 $T_n$ 的值。

示例 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} - 1$。

---

动态规划（迭代）

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

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

Java 代码：

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;
    }
}

C++ 代码：

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;
    }
};

Python 代码：

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n == 2: return 1
        a, b, c = 0, 1, 1
        for i in range(3, n + 1):
            d = a + b + c
            a, b, c = b, c, d
        return c

TypeScript 代码：

function tribonacci(n: number): number {
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;
    let a = 0, b = 1, c = 1;
    for (let i = 3; i <= n; i++) {
        const d = a + b + c;
        a = b; b = c; c = d;
    }
    return c;
};

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

---

动态规划（递归）

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

Java 代码：

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];
    }
}

C++ 代码：

class Solution {
public:
    vector<int> cache = vector<int>(40, 0);
    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];
    }
};

Python 代码：

class Solution:
    def __init__(self):
        self.cache = [0] * 40
    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n == 2: return 1
        if self.cache[n] != 0: return self.cache[n]
        self.cache[n] = self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
        return self.cache[n]

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

---

矩阵快速幂

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

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

矩阵快速幂用于求解一般性问题：给定大小为 $n \times n$ 的矩阵 $M$，求答案矩阵 $M^k$，并对答案矩阵中的每位元素对 $P$ 取模。

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

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

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

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

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

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

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

$$\begin{bmatrix} f(i - 1)\\ f(i - 2)\\ f(i - 3) \end{bmatrix}$$

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

$$\begin{bmatrix} f(i)\\ f(i - 1)\\ f(i - 2) \end{bmatrix}$$

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

$$\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}$$

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

$$\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}$$

我们令

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

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

$$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 * \begin{bmatrix} f(i )\\ f(i - 1)\\ f(i - 2) \end{bmatrix} = \begin{bmatrix} f(i + 1)\\ f(i)\\ f(i - 1) \end{bmatrix}$$

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

$$\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}$$

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

Java 代码：

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];
    }
}

C++ 代码：

class Solution {
public:
    int N = 3;
    vector<vector<long long>> mul(vector<vector<long long>>& a, vector<vector<long long>>& b) {
        vector<vector<long long>> c(N, vector<long long>(N, 0));
        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;
    }
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        vector<vector<long long>> ans = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        vector<vector<long long>> mat = {{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];
    }
};

Python 代码：

class Solution:
    def __init__(self):
        self.N = 3

    def mul(self, a, b):
        c = [[0] * self.N for _ in range(self.N)]
        for i in range(self.N):
            for j in range(self.N):
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]
        return c

    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n == 2: return 1
        ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
        mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
        k = n - 2
        while k != 0:
            if k & 1: ans = self.mul(ans, mat)
            mat = self.mul(mat, mat)
            k >>= 1
        return ans[0][0] + ans[0][1]

TypeScript 代码：

function tribonacci(n: number): number {
    const N = 3;
    const mul = function(a: number[][], b: number[][]): number[][] {
        const c = Array.from({ length: N }, () => Array(N).fill(0));
        for (let i = 0; i < N; i++) {
            for (let 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;
    };
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;
    let ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];
    let mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]];
    let k = n - 2;
    while (k !== 0) {
        if (k & 1) ans = mul(ans, mat);
        mat = mul(mat, mat);
        k >>= 1;
    }
    return ans[0][0] + ans[0][1];
};

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

---

打表

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

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

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

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

Java 代码：

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];
    }
}

C++ 代码：

class Solution {
public:
    static vector<long long> cache;
    Solution() {
        cache.resize(40);
        cache[0] = 0; cache[1] = 1; cache[2] = 1;
        for (int i = 3; i < 40; ++i) {
            cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
        }
    }
    int tribonacci(int n) {
        return static_cast<int>(cache[n]);
    }
};
vector<long long> Solution::cache;

Python 代码：

class Solution:
    cache = [0, 1, 1] + [0] * 37
    for i in range(3, 40):
        cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]

    def tribonacci(self, n: int) -> int:
        return self.cache[n]

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

---

最后

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

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

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

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