1137. 第 N 个泰波那契数

Posted on | In
Words count in article: 233 | Reading time ≈ 1

题目

泰波那契序列 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。

解法

解法一：

JAVA

1
2
3
4
static int[] Ts = {0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, 2082876103};
    public int tribonacci(int n) {
        return Ts[n];
    }

解法二：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int tribonacci(int n) {
        if (0 == n) {
            return 0;
        }

        if (2 >= n) {
            return 1;
        }

        int t0 = 0;
        int t1 = 1;
        int t2 = 1;

        int result = 0;
        for (int i = 3;i <= n;i++) {
            result = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = result;
        }
        return result;
    }
0%