动态规划 —— 斐波那契数列模型-第 N 个泰波那契数

1. 第 N 个泰波那契数

题目链接： 1137. 第 N 个泰波那契数 - 力扣（LeetCode）

https://leetcode.cn/problems/n-th-tribonacci-number/

Tn+3 = Tn + Tn+1 + Tn+2 可以转换为 Tn = Tn-3 + Tn-2 + Tn-1

由上图可以看出T3等于T0+T1+T2,T4=T1+T2+T3以此类推后面的数

2. 算法原理

1. 状态表示：dp表里的值所代表的含义

本题状态表式是：第i个泰波那契数的值（先根据画的图来看（第i个,最后返回值按照题目的要求来））

2.状态转移方程 本题的状态转移方程 就是 dp[i]等于什么 ：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

3. 初始化：把dp表填满不越界 如何填表：就是根据前面的状态转移方程来进行填表 比如：如果我们想要填dp[4]的值，那么我们只需要知道前面3个dp的值再相加就行了

不越界就是：如果我们想要填dp[0]的值，那么我们就需要dp[0]前3个dp的值相加，那么就会造成越界访问的问题，还有题目的数据范围

本题的初始化就是：dp[0] = 0 ; dp[1] = dp[2] = 1 ;

4. 填表顺序 本题的填表顺序是：从左到右

5. 返回值 ：题目要求 + 状态表示 本题的返回值是：直接返回dp[n]

3. 代码

动态规划的固定四步骤：1. 创建一个dp表 2. 在填表之前初始化 3. 填表（填表方法：状态转移方程） 4. 确定返回值

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[0]=0;
        dp[1]=dp[2]=1;
        //前三个题目已经初始化好了，从dp[3]开始初始化
        for(int i=3;i<=n;i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
            return dp[n];
    }
};

感谢观看~