本文主要是介绍斐波那契数列模型-----第N个泰波那契数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
动态规划五个关键点：
1、状态表示：可以理解为dp数组中每一个数dp[i]的含义。怎么得来？（1、题目要求。2、经验+题目要求。3、分析问题的过程中，发现重复子问题。）
2、状态转移方程：即可以认为dp[i] = ？
3、初始化：怎么样初始化dp表，需要根据状态转移方程和题意来确定。
4、填表顺序：为了填写当前状态的时，要保证所需要的状态已经计算过了。
5、返回值：返回题目要求的某一个状态。
本题中：
状态表示：dp[i] 代表第i个泰波那契数的数值。
状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
初始化：首先要保证dp数组不越界，本题仅需初始dp[0] = 0,dp[1]=1,dp[2] = 2。
填表顺序：当前状态dp[i]由前三个状态决定，所以从左向右填表。
返回值：返回状态表中 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表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];//返回值}
};分析时间复杂度：O(N)，空间复杂度O(N)。
空间优化：
关于动态规划的空间优化，一般都是用滚动数组来优化。
| i | 0 | 1 | 2 | 3 | 4 |
| dp[i] | 0 | 1 | 1 | 2 | 4 |
我们发现，求dp[i]的状态只需要前面三个状态，前三个数之前的状态就相当于浪费空间了。
那么就是在求dp[i]的时候，我们仅需要dp[i]前面的若干个状态时，我们就可以用滚动数组。
滚动数组的好处：
当原本空间复杂度为O(N^2)时，优化成O(N)；原本为O(N)的，优化成O(1)。即仅需要几个变量，就可以完成一道题。
class Solution {
public:int tribonacci(int n) {//处理边界问题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;}
};或者真的用一个数组：
class Solution {
public:int tribonacci(int n) {//处理边界问题if(n == 0) return 0;if(n == 1 || n == 2)return 1;vector<int> roll(4);roll[0] = 0,roll[1] = roll[2] = 1,roll[3] = 0;for(int i = 3;i<=n;i++){roll[3] = roll[0] + roll[1] + roll[2];roll[0] = roll[1];roll[1] = roll[2];roll[2] = roll[3];}return roll[3];}
};这篇关于斐波那契数列模型-----第N个泰波那契数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
