本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。
💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
专题一
- 题目来源
- 题目描述
- 题目解析
- 算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值
- 代码实现
题目来源
本题来源为：
Leetcode1137. 第 N 个泰波那契数
题目描述
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
题目解析
这里我们首先可以先将题目的公式变形一下：
通过一个简单例子来理解此题目：
T0 T1 T2值题目中已经给出，而T4的值是T0 +T1+ T2的结果，而T5的值是T1 +T2+ T3的结果，依次内推…
算法原理
在讲解此题的算法原理之前，我们先了解一下动态规划：
[动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。
可能此概念对于初学者来说很抽象，我们通过本题为例，给出动态规划的一般解决思路：
动态规划做题流程，一般会定义一个dp(动态规划的缩写)表(一位或者二维数组)
然后想办法把里面的值给填满，里面的某一个值可能就是我们的最终结果！
举个例子：
动态规划基本上分为五步:
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
其中状态转移方程由状态表示推出，而3.4.5步则为处理细节问题。
接下来将通过本题为例来讲解这五步如何处理：
1.状态表示
首先什么是状态表示呢？
简单点的说：状态表示就是dp表里面值的含义
那么具体怎么知道里面值所代表的含义呢？
基础有三种方式
1.1题目要求
1.2经验+题目要求(大多数)
1.3分析问题过程中，发现重复子问题(难点)
当然也不仅仅与此，后面也会再接触更多的方法！
那么根据本题目要求，
dp[i]表示：第i个泰波那契的值
2.状态转移方程
状态转移方程是什么？
通俗来说，就是推出一个式子，让dp[i]等于什么
根据本题要求，我们计算一个值时，需要知道它前面的三个值。
计算i位置的值（dp[i]）时，需要知道i-1,i-2,i-3的值，那么i-1位置的值又怎么求呢？在回顾一下我们的状态表示，dp[i]表示：第i个泰波那契的值 那么i-1位置的值不就是dp[i-1]，以此内推…
分析到这，我们的状态转移方程已经出来了：
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
3.初始化
什么是初始化？
就是要保证填表的时候不越界
那么怎么填，其实就是根据状态转移方程，害怕越界访问，进行相关初始化 而本题的题目其实已经告诉我们了：
当i为0,1,2时就会产生越界访问，而本题的题目已经将这三个位置的值已经告诉我们了：
因此初始化为：
dp[0]=0
dp[1]=1
dp[2]=2
4.填表顺序
根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右
5.返回值
根据题目要求返回第 n 个泰波那契数 Tn 的值。
而我们的状态表示 ：dp[i]表示：第i个泰波那契的值
因此返回dp[n]
代码实现
动态规划的代码基本就是固定的四步：
1.创建dp表
2.初始化
3.填表
4.返回值
class Solution
{
public:
int tribonacci(int n)
{
// 1.创建dp表
// 2.初始化
// 3.填表
// 4.返回值
//处理一下边界情况：
if(n==0)
return 0;
if(n==1||n==2)
return 1;
//创建dp表
vector<int> dp(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];
}
};
注意n的取值范围：
0 <= n <= 37
因此要处理一下边界情况：
//处理一下边界情况
if(n==0)
return 0;
if(n==1||n==2)
return 1;
时间复杂度：O(N)
空间复杂度：O(N)
