文章目录
- 题目
- 讲解算法原理
- 代码实现
题目
题目如下：
讲解算法原理
我们先说一下动态规划题目的整体做题思路：
- 第一步： 状态表示
什么是状态表示?
做动态规划类题目一般会定义一个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】。
代码实现
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];}
};
