1137-第 N 个泰波那契数(N-th Tribonacci Number)

原文链接: https://leetcode-cn.com/problems/n-th-tribonacci-number

英文原文

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:


Input: n = 4

Output: 4

Explanation:

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

Example 2:


Input: n = 25

Output: 1389537

Constraints:

<li><code>0 &lt;= n &lt;= 37</code></li>

<li>The answer is guaranteed to fit within a 32-bit integer, ie. <code>answer &lt;= 2^31 - 1</code>.</li>

中文题目

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

T₀ = 0, T₁ = 1, T₂ = 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。

通过代码

高赞题解

欢迎关注我 ❤️ 提供写「证明」&「思路」的高质量专项题解
更有「长期送实体书」活动等你来 🎉 🎉

迭代实现动态规划

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

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

代码：

[]
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(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)$

矩阵快速幂

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

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

矩阵快速幂用于求解一般性问题：给定大小为 $n * 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}$ ，这时候可以套用「矩阵快速幂」解决方案。

代码：

[]
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(1)$

打表

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

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

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

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

考虑到可能会有不熟 Java 的同学，static 修饰的作用是「在 Solution 被实例化前，cache 已经被计算好，并且只会被计算一次」。

代码：

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

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

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

统计信息

通过次数	提交次数	AC比率
90598	148663	60.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
爬楼梯	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途