【动态规划】斐波那契数列模型

欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：题目大解析（3）

---

前言
算法原理

1.状态表示
是什么？dp表(一维数组)里面的值所表示的含义
怎么来？
（1）：题目要求 （2）：经验+题目要求 (3) :分析问题的过程中，发现重复子问题

2.状态转移方程
dp[i] = ?

3.初始化
保证填表的时候不越界

4.填表顺序
为了填写当前状态的时候，所需要的状态已经计算过了

5.返回值
题目要求+状态表示

编写代码四步骤：创建dp表->初始化->填表->返回值

---

👉🏻第 N 个泰波那契数

原题链接：第 N 个泰波那契数

mycode:

class Solution {
public:int tribonacci(int n) {//处理dp表可能越界情况if(n==0)return 0;if(n==1||n==2) return 1;//1.建表vector<int> v(n+1);//2.初始化v[0] = 0,v[1] = v[2] = 1;//3.填表for(int i = 3;i<=n;i++)v[i] = v[i-3]+v[i-2]+v[i-1];//返回值return v[n];}
};

空间优化

class Solution {
public:int tribonacci(int n) {//处理dp表可能越界情况if(n==0)return 0;if(n==1||n==2) return 1;int a = 0,b = 1,c = 1,d = 0;//3.填表for(int i = 3;i<=n;i++){d = a+b+c;a = b;b = c; c = d;}//返回值return d;}
};