本文主要是介绍【算法学习】第N个泰波那契数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述
题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
二、解析题目
常规并且简单的动态规划题目，根据动规步骤一步步来即可。
动态规划的题围绕着dp表展开的。此题根据题目信息是一个线性的递推过程，一维dp表即可。
1.状态表示
对于状态，我的通俗理解是dp表中值的意义或者什么意思。因为我们是要求解第n个泰波那契数，那么dp[i]就表示是第i个泰波那契数的值了。
2.递推公式
根据题目，提取出关键信息：在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2。
转换一下，可以得到：Tn = Tn-3 + Tn-2 + Tn - 1;(n >=3)。
这也是之后计算dp表每个值的递推公式。
3.初始化
初始化的目的是为了dp在填表过程中不会发生数组越界。因为n>=3，所以这里初始化我们需要给初始的三个值0、1、2赋值。（根据题目赋予的值为0、1、1）
4.填表顺序
需要从左到右依次填表。因为递推公式需要的是此下标的前三个下标对应值的累和。
5.返回值
返回值就是对应的dp[n]。
正常的dp题流程到此结束。分析上述算法，空间复杂度On（数组n+1的大小），时间复杂度On（迭代循环）。但是此题根据递推公式可以发现在计算某一状态值时，利用的只是前面三个状态的值，为此我们可以进行空间优化。
空间优化
我们可以利用滚动数组的思维方式进行空间优化。
在原本创建dp表的这一步，我们只需要替换为四个变量即可，前三个表示前三个状态，第四个表示现在我正在求的状态值，循环迭代的时候计算完当前状态值，前三个变量重新赋值即可，只需要保持时前三个状态的值。
这样，我们就可以把之前的On大小的空间优化为O1（只有变量的空间）。
三、代码参考
1.常规思路
class Solution {
public:int tribonacci(int n) {// 越界处理if (n == 0) return 0;if (n < 3) return 1;//1创建dp表vector<int> dp(n + 1);//2初始化dp[0] = 0, dp[1] = dp[2] = 1;//3填表for (int i = 3; i <= n; ++i)dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];return dp[n];}
};2.空间优化思路
class Solution {
public:int tribonacci(int n) {// 越界处理if (n == 0) return 0;if (n < 3) return 1;// 优化空间// 滚动数组解决问题：仅仅需要前面的几种状态值// 1初始化int a, b, c, d;a = d = 0;b = c = 1;// 2循环迭代for (int i = 3; i <= n; ++i){d = a + b + c;a = b;b = c;c = d;}return d;}
};这篇关于【算法学习】第N个泰波那契数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
