一、题目

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.

---

二、解法

规律：Tn = Tn-1 + Tn-2 + Tn-3

(1) 递归解法(超时)

public int tribonacci(int n) { if(n <= 0) return 0; if(n == 1 || n == 2) return 1; return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3); }

(2) 迭代

序列是前 3 项和是第 4 项的值，非递归的话，就要人为地构造。

public int tribonacci(int n) { if(n <= 0) return 0; if(n == 1 || n == 2) return 1; int t0 = 0, t1 = 1, t2 = 1； int sum = 0; for(int i = 4; i < n+2; i++) { sum = t0+t1+t2; t0 = t1; t1 = t2; t2 = sum; } return t2; }

解释：（1）为什么 i < n+2 ？（2）为什么 return t2？

因为一次循环，变化的是前3项，也就是当序列为 0, 1, 1, 2 时，一次循环后，序列变为 1，1，2，2，可以发现第四项没有变化，故返回第四项，必须进行2次循环。t2 是当前循环的 t0+t1+t2 的和，故它代表最后要求的项。