【动态规划专栏】专题一：斐波那契数列模型--------1.第N个泰波那契数

题目来源

本题来源为：

Leetcode1137. 第 N 个泰波那契数

题目描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

题目解析

这里我们首先可以先将题目的公式变形一下：

通过一个简单例子来理解此题目：

T₀ T₁ T₂值题目中已经给出，而T₄的值是T₀ +T₁+ T₂的结果，而T₅的值是T₁ +T₂+ T₃的结果，依次内推…

算法原理

在讲解此题的算法原理之前，我们先了解一下动态规划：

[动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

可能此概念对于初学者来说很抽象，我们通过本题为例，给出动态规划的一般解决思路：

动态规划做题流程，一般会定义一个dp(动态规划的缩写)表(一位或者二维数组)

然后想办法把里面的值给填满，里面的某一个值可能就是我们的最终结果！

举个例子：

动态规划基本上分为五步:

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

其中状态转移方程由状态表示推出，而3.4.5步则为处理细节问题。

接下来将通过本题为例来讲解这五步如何处理：

1.状态表示

首先什么是状态表示呢？

简单点的说：状态表示就是dp表里面值的含义

那么具体怎么知道里面值所代表的含义呢？

基础有三种方式

1.1题目要求

1.2经验+题目要求(大多数)

1.3分析问题过程中，发现重复子问题(难点)

当然也不仅仅与此，后面也会再接触更多的方法！

那么根据本题目要求，

dp[i]表示：第i个泰波那契的值

2.状态转移方程

状态转移方程是什么？

通俗来说，就是推出一个式子，让dp[i]等于什么

根据本题要求，我们计算一个值时，需要知道它前面的三个值。

计算i位置的值（dp[i]）时，需要知道i-1,i-2,i-3的值，那么i-1位置的值又怎么求呢？在回顾一下我们的状态表示，dp[i]表示：第i个泰波那契的值 那么i-1位置的值不就是dp[i-1]，以此内推…

分析到这，我们的状态转移方程已经出来了：

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

3.初始化

什么是初始化？

就是要保证填表的时候不越界

那么怎么填，其实就是根据状态转移方程，害怕越界访问，进行相关初始化 而本题的题目其实已经告诉我们了：

当i为0,1,2时就会产生越界访问，而本题的题目已经将这三个位置的值已经告诉我们了：

因此初始化为：

dp[0]=0
dp[1]=1
dp[2]=2

4.填表顺序

根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右

5.返回值

根据题目要求返回第 n 个泰波那契数 Tn 的值。

而我们的状态表示 ：dp[i]表示：第i个泰波那契的值

因此返回dp[n]

代码实现

动态规划的代码基本就是固定的四步：

1.创建dp表
2.初始化
3.填表
4.返回值

class Solution 
{
public:
    int tribonacci(int n) 
    {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
      
        //处理一下边界情况：
        if(n==0)
            return 0;
        if(n==1||n==2)
            return 1;
        //创建dp表
        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];
    }
};

注意n的取值范围：

0 <= n <= 37

因此要处理一下边界情况：

//处理一下边界情况
 if(n==0)
    return 0;
 if(n==1||n==2)
    return 1;

时间复杂度：O(N)

空间复杂度：O(N)