题目
题目如下：
在这里插入图片描述讲解算法原理
我们先说一下动态规划题目的整体做题思路：
- 第一步： 状态表示
什么是
状态表示? 做动态规划类题目一般会定义一个dp表。这个dp表一般为一维数组或者二维数组。然后把这个表给填满，其中的一个值就有可能是我们想要的结果。 状态表示就是dp表中的某一个值所表示的含义
状态表示是怎么来的呢？得到状态表示的途径无非有以下几种：①题目要求。②经验 题目要求。③分析问题的过程中，发现重复的子问题
本题属于比较简单的题目，根据题目要求即可。题目中说：存在第0个数，那么第N个数就和dp数组中N下标的元素相对应。 所以本题的状态表示为：dp[i]表示第i个泰波那锲数
- 第二步：状态转移方程
dp[i]等于什么？这就是状态转移方程。 在本题中：dp【i】=dp【i-1】 dp【i-2】 dp【i-3】。这个就是状态转移方程，而得到状态转移方程的途径就是题目描述。 所以，这一步也是装备转移方程最难的一步。 接下来的几步都是在处理细节的问题。
- 第三步：初始化
要求就是：保证填表的时候不越界
怎么填表？根据状态转移方程填表。然后在两端的位置进行分析。
- 第四步：填表顺序
要求就是：为了保证填写当前位置的时候，所需的位置已经填写过了。 什么意思？用这道题目来分析一下。
填写n位置时，必须保证n-1，n-2，n-3位置的数据已经获得。所以我们要从左向右进行填表。
-第五步： 返回值
题目要求什么我们就返回什么。一般都是返回dp【n】。
代码实现
代码语言：javascript复制class Solution {
public:
int tribonacci(int n) {
if(n==0) return 0;
if(n==1||n==2)return 1;
vector<int> dp(n 1);
dp[0]=0;
dp[1]=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];
}
};
