力扣题目链接：
题目
第N个泰波那锲数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
示例 2：输入：n = 25 输出：1389537
思路
普通思路
看到这个的时候，我们会想到我们之前学的那个斐波那契数，实际上，这两个确实是有联系的，是同一个类型的，分析给出的泰波那锲数列的定义“T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2”先是给出这个数列的前三个值，后又给出一个公式，这个公式不难看出，第n 项等于前三项之和，前提是n大于等于3，为什么要大于等于三呢，这是因为，这个数列从第0项开始，如果n是第二项，第二项只有前两项（第0项和第1项），没有前三项，不能用这个公式，所以题目也给出了，第0项，第1项，第2项的值，这样一步一步就可以算出数列里面各项了。
动态规划
这样看起来也不难，但是我们在这里要学习动态规划，接下来就说说动态规划的思路
动态规划原理
动态规划做题步骤一般我们会先定义一个dp表（一个一维数组或者一个二维数组，然后用dp来命名），然后把这个表填满，这样里面的某一个值可能我们想要的结果。
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
1.状态表示
dp表里面的值表示的含义就是一个状态表示。
状态表示简单题可以通过题目要求获取（比如这个题，状态表示就是数列里面的值）或者就是经验+题目要求（经验就是要我们多做题 一百到两百道题目），再或者分析题目发现子问题（就是把一个题目，分解成多个小问题）
对于本题，我们可以直接根据题目要求来确定状态表示，dp表就是这个泰波那锲数列dp[i],dp[0]表示第0个泰波那锲数，dp[1]表示第1个泰波那锲数，dp[i]表示第i个泰波那锲数。最后返回第n个泰波那锲数就可以了。
这一步是做动态规划题最重要的一步！！！！！
2.状态转移方程
状态转移方程就是：dp[i]等于什么？
对于本题 ，dp[i]就是第i个数，根据上面普通思路的分析，第i个数等于前三个数之和，
dp[i]=dp[i-1]+dp[i-2]+dp[i-3],所以这个就是此题的状态转移方程。
这一步是做动态规划题最难的一步！！！！！
3.初始化
初始化就是：保证填表的时候不越界，对该初始化的值要进行初始化
对于本题,n是大于等于0的，所以小于0的都算是访问越界。状态转移方程dp[i]=dp[i-1]+dp[i-2]+dp[i-3],
当i=0时，dp[0]=dp[-1]+dp[-2]+dp[-3]
当i=1时，dp[1]=dp[0]+dp[-1]+dp[-2]
当i=2时，dp[2]=dp[1]+dp[0]+dp[-1]
可见在计算第0项，第1项，第2项时都会访问越界，所以需要初始化第0项，第1项，第2项（题目已给出值）。
4.填表顺序
确定填表顺序是为了填写当前状态时，所需要的状态已经计算过了
对于本题，加入我们要计算第3项开始算，我们需要知道，第0项，第1项，第2项，计算第4项，要知道第1项，第2项，第3项，所以要算第4项，必须先算第3项，其他依次类推，得出，填表顺序，必须是从左往右填写。
5.返回值
根据题目要求和状态表示返回我们要的答案
对于本题,我们要求第n个泰波那锲数的值，所以返回dp[n]就行。
代码
动态规划写代码四步
1.创建dp表
2.初始化
3.填表
4.返回值
另外这个需要注意一下，如果n=0,n=1,n=2需要单独处理。
int tribonacci(int n) { //创建dp int dp[1000]={0}; //初始化 dp[0]=0; dp[1]=1; dp[2]=1; //边界 if(n==0)return 0; if(n==1||n==2)return 1; //填表 for(int i=3;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } //返回值 return dp[n]; }
空间复杂度：O(n)
时间复杂度：O(n)
空间优化
某一个状态的前若干个状态，其他的没有用这种情况下可以使用滚动数组（有限的变量来代替之前的dp数组）
每次进行赋值操作，进行滚动（a=b,b=c,c=d)
int tribonacci(int n) { //初始化 int a=0,b=1,c=1,d=0; //边界 if(n==0)return 0; if(n==1||n==2)return 1; while(n>2) { //计算 d=a+b+c; //滚动操作 a=b;b=c;c=d; n--; } return d; }
