1.题目：
2.解析：
动态规划解题模板解释：
本题：
1.状态方程：dp[i]第i个泰波那契数
2.状态转移方程：根据题意得：把Tn 3 = Tn Tn 1 Tn 2，
变为Tn = Tn-3 Tn-2 Tn-1。
3.初始化：先把dp[0] = 0; dp[1] = dp[2] = 1; 初始化好就不会越界。
4.填表顺序：从左往右
5.返回值：返回dp[n]
代码：
代码语言：javascript复制public int tribonacci(int n) {
/**
代码书写模板：
1.创建dp表
2.初始化
3.填表
4.返回值
*/
//边界情况：
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int[] dp = new int[n 1];
dp[0] = 0; dp[1] = dp[2] = 1;
for(int i = 3; i <= n;i )
dp[i] = dp[i-1] dp[i-2] dp[i-3];
return dp[n];
}利用滚动数组优化后代码：
注意：滚动数组优就是，定义几个变量来滚动得到dp表；
时间和空复杂度会降序一个量级：从O(N) 到 O(1) ....
代码语言：javascript复制//滚动数组优化版本：
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int a = 0, b = 1, c = 1, d = 0;
for(int i = 3; i <= n;i ){
d = a b c;
a = b;
b = c;
c = d;
}
return d;
}
