求第 N 个泰波那契数 | 动态规划
1.第 N 个泰波那契数
题目连接：1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
2.什么是动态规划
在解决这道问题之前先来了解一下，什么是动态规划。动态规划（Dynamic Programming）：简称 DP，是一种求解多阶段决策过程最优化问题的方法。简单的理解，把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。
它的核心思想是，把「原问题」分解为「若干个重叠的子问题」，将子问题计算出来的结果存放到一张dp表中，通过dp表中过往计算的结果，来减少计算并计算出原问题。
它的解题步骤大致分为五个过程：状态表⽰、状态转移⽅程、初始化、填表顺序、返回值！
3.解决问题
(1)、状态表示
我们需要将子问题存放到，一张dp表中，而dp[i]就表示状态。对应这里的状态即为，dp[i] = 第 i 个泰波那契数的值。
(2)、状态转移⽅程
这道题，就已经将状态转移方程给出，我们稍微变形：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
(3)、初始化
由于dp[0]，dp[1]，dp[2]的数值题目以给出，直接将值填入dp表中，完成初始化。初始化时需要注意，确保dp表下标不要越界。
(4)、初始化顺序
这里根据题目要求，根据状态转移方程，将dp填充。
(5)、返回值
返回dp[n]即为，返回结果。
4.参考代码
C++版本：
class Solution
{
public:int tribonacci(int n) {vector<int> dp(n + 3,0);dp[1] = dp[2] = 1; for(int i = 3;i <= n;i++){dp[i] = dp[i-3] + dp[i - 2] + dp[i -1];}return dp[n];}
};
Python3版本：
class Solution:def tribonacci(self, n: int) -> int:list = [0, 1, 1]for i in range(3, n + 1):next_value = list[i - 3] + list[i - 2] + list[i - 1]list.append(next_value)return list[n]
5.空间优化
在上面的代码当中，空间的复杂度为O(N)。关于这道题，我们求出dp[n]的值，只需要求n前三个状态。所以我们就可以使用滚动数组的方案来优化空间。如果，求dp[n]只需要n前的若干个状态，那么就可以使用滚动数组优化。
优化代码C++版本：
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,c] 不能后往前赋值[c,b,a]a = b;b = c;c = d;}return d;}
};