一、斐波那契数列模型_第 N 个泰波那契数_C++

1.题目

2.讲解算法原理

1.状态表示

dp表里面某个位置值所表示的含义

怎么来？

题目要求—————dp[i]表示：第i个泰波那契数的值

经验 + 题目要求

分析问题的过程中，发现重复子问题

2.状态转移方程

dp[i]等于什么

3.初始化

保证填表时不越界

根据推出的状态转移方程可知-1，-2，-3会存在，所以前三个赋值

4.填表顺序

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

从左向右

5.返回值

题目要求+状态表示

dp[n]

3、代码

class Solution
{
public:
    int tribonacci(int n)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值

        // 处理一些边界情况
        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;
        for(int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};

二、斐波那契数列模型_三步问题