【动态规划篇】1137. 第 N 个泰波那契数

前言：

动态规划问题一般分为五步：

1. 先确定一个状态表示
2. 根据状态表示来推导状态方程
3. 初始化
4. 填表顺序
5. 返回值

①状态表示

• 先创建一个以为数组，起名为dp,这个一维数组就叫做dp表
  
• 把dp表填满，填满后的某个值就是我们想要的结果
• 状态表示是什么呢？dp表中某个值所表示的含义 。
• 怎么来的呢？ⓐ根据题目要求ⓑ经验+题目要求ⓒ分析题目过程中发现重复子问题

➁状态转移方程（即dp[i]是什么）

• 例如下面的这道题中的dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

➂初始化

• 保证填表的时候不越界，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，所以前三个位置会越界
• 初始化 dp[0] = 0, dp[1] = dp[2] = 1

➃填表顺序

• 为了填写当前状态的时候，所需要的状态已经算过了

➄返回值

• 题目要求+状态表示

1137. 第 N 个泰波那契数

题目链接： 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

---

解题思路：

1. 状态表示
   创建一个dp表，让dp表中dp[0]表示第0个泰波那契数，dp[1]表示第1个泰波那契数…dp[i]表示第i个泰波那契数
2. 状态转移方程
   题目中为 Tn+3 = Tn + Tn+1 + Tn+2处理一下得 Tn = Tn-3 + Tn-2 + Tn-1,所以状态方程为dp[i] = dp[i-1]+ dp[i-2] + dp[i-3]
3. 初始化
   dp[0] = 0,dp[1] = dp[2] = 1
4. 填表顺序
   要求填4的时候3已经计算过了，所以填表顺序为从左向右
5. 返回值
   返回dp[i]

代码实现：

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] = 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)

---

动态规划空间优化 -滚动数组
 求dp[4]的时候dp[0]相当于浪费空间，当我们求后面的某个值时，前面的有些值我们就不需要了，这个时候就可以用 滚动数组来优化。

abc求完d后，abc滚到下面
代码实现：

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;}
};

---

👍 如果对你有帮助，欢迎：

• 点赞 ⭐️
• 收藏 📌
• 关注 🔔