第N个泰波那契数是什么？

本文共计640个文字，预计阅读时间需要3分钟。

题目描述：泰波那契序列，且在n=0的条件下，给你整数n，请返回第n个泰波那契数。泰波那契序列定义如下：T_0=0T_1=1T_2=1对于n > 2，T_n=T_{n-1} + T_{n-2} + T_{n-3}

示例1：输入：n=4输出：4解释：T_3=0 + 1 + 1=2T_4=1 + 1 + 2=4

示例2：输入：n=25输出：...解释：结果超出100个字符限制

题目描述

泰波那契序列

, 且在 n >= 0的条件下

给你整数 ​​n​​ ，请返回第 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​​。

题目分析

这道题跟斐波那契数列的计算方法一致，这道题我们还是使用类似动态规划的方法解决。可以看到泰波那契数列的计算公式如下：

可以看到，从第四个泰波那契数开始，泰波那契数由前三个泰波那契数相加得到，所以我们可以维护三个变量，分别存储前三个泰波那契数，再由这三个数计算得到下一个泰波那契数，计算的同时更新这三个变量。

题解

执行用时: 0 ms

内存消耗: 38.2 MB

class Solution {
public int tribonacci(int n) {
if (n == 0) {
// f(0) = 0
return 0;
} else if (n == 1 || n == 2) {
// f(1) = f(2) = 1
return 1;
}
int p1 = 0, p2 = 1, cur = 1;
for (int i = 3; i <= n; ++i) {
int sum = p1 + p2 + cur;
p1 = p2;
p2 = cur;
cur = sum;
}
return cur;
}
}

题目来源:力扣(LeetCode)