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

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

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)