1、第 N 个泰波那契数（easy）

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

​ T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2。给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

• 0 <= n <= 37

• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1

---

因为这是我们接触到的第一道动态规划题，所以要先知道一些概念，也就是动态规划的算法原理，它可以说分为以下几个步骤：

1. 状态表示：简单地说，就是 dp[i] 表示什么！
   • 题目要求
   • 经验（多刷题）+ 题目要求
   • 分析问题过程中发现重复子问题
2. 状态转移方程：简单地说，就是 dp[i] 如何通过已知的状态得到！
3. 初始化
4. 填表
5. 返回值

​ 其中最重要的就是第一点，因为我们解题之前必须先搞清楚要的是什么一个状态，而最难的其实是第二点，得到状态转移方程，得到这个方程之后，基本这道题就解决了！

​ 除此之外还有一个步骤就是空间优化，这个只会在我们这道题和后面的背包问题会涉及到，因为最重要的不是空间优化，而是理解如何得到状态方程！

解题思路

​ 对于这道题，其实是不难的，首先确定我们的状态，这里只需要一维状态表即可，也就是一维数组，起名叫做 dp 吧，以后都是这样子的！

​ 对于这个状态表示，dp[i] 不用说，很明显表示第 i 个泰波那契数！

​ 对于状态转移方程，这道题直接给出了，所以说这道题不难，但是我们写成转移方程的时候一般都用 dp[i] 来表示，而不是题目中的 dp[i+3] 这样子，所以方程就是 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

class Solution {
public:int tribonacci(int n) {// 创建dp表int dp[38];// 初始化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];}
};

​ 至于空间优化，其实很明显吧，因为每次其实我们用到的就是三个变量来推导，所以我们只需要用三个状态变量，加上一个结果变量来进行状态转移即可，就不用去开辟数组了，节省了空间，只不过要注意的是赋值顺序不要搞错了！

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, ret = 0;// 通过状态转移方程填表for(int i = 3; i <= n; ++i){ret = a + b + c;a = b;b = c;c = ret;}// 返回值return ret;}
};