The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
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:
0 <= n <= 37- The answer is guaranteed to fit within a 32-bit integer, ie.
answer <= 2^31 - 1.
第 N 个泰波那契数。
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载只要理解请联系官方授权，非商业转载请注明出处。
这道题几乎就是70题爬楼梯的翻版，只要理解泰波那契数的定义，就不难写出来，某一个数字是其前三个数字的加和。如果不理解，可以先做 70 题或 509 题。
时间O(1) - 因为 N 的范围最大就到37
空间O(1)
Java实现
1 class Solution { 2 public int tribonacci(int n) { 3 // corner case 4 if (n == 0) { 5 return 0; 6 } 7 if (n == 1 || n == 2) { 8 return 1; 9 } 10 11 // normal case 12 int a = 0; 13 int b = 1; 14 int c = 1; 15 int d = 1; 16 for (int i = 3; i <= n; i++) { 17 d = a + b + c; 18 a = b; 19 b = c; 20 c = d; 21 } 22 return d; 23 } 24 }
相关题目