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

欢迎来到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;
    }
};