LeetCode1137-第N个泰波那契数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/n-th-tribonacci-number/

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

题目详述

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

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

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

示例 1：

1
2
3
4
5
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

1
2
输入：n = 25
输出：1389537

提示：

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

题目详解

斐波那契改为了泰波那契，按要求进行递推即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_01137 {

    static int[] f = new int[38];

    static {
        f[1] = f[2] = 1;
        for (int i = 3; i < 38; ++i) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
    }

    public int tribonacci(int n) {
        return f[n];
    }
}

可以运用滚动数组进行优化，降低空间复杂度。

1
2
3
4
5
6
7
8
9
10
public class LeetCode_01137 {

    public int tribonacci(int n) {
        int[] f = new int[]{0, 1, 1, 2};
        for (int i = 4; i <= n; ++i) {
            f[i % 4] = f[(i - 1) % 4] + f[(i - 2) % 4] + f[(i - 3) % 4];
        }
        return f[n % 4];
    }
}