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

03-01 1160阅读 0评论

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

$【动态规划专栏】专题一：斐波那契数列模型--------1.第N个泰波那契数,【动态规划专栏】专题一：斐波那契数列模型--------1.第N个泰波那契数,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,访问,方法,第1张$

（图片来源网络，侵删）

💓博主csdn个人主页：小小unicorn

⏩专栏分类：动态规划专栏

🚚代码仓库：小小unicorn的代码仓库🚚

🌹🌹🌹关注我带你学习编程知识

专题一

题目来源
题目描述
题目解析
算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值
- 代码实现
  题目来源
  
  本题来源为：
  
  Leetcode1137. 第 N 个泰波那契数
  $【动态规划专栏】专题一：斐波那契数列模型--------1.第N个泰波那契数,【动态规划专栏】专题一：斐波那契数列模型--------1.第N个泰波那契数,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,访问,方法,第2张$
  （图片来源网络，侵删）
  
  题目描述
  
  泰波那契序列 Tn 定义如下：
  T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
  给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
  
  题目解析
  
  这里我们首先可以先将题目的公式变形一下：
  T0 T1 T2值题目中已经给出，而T4的值是T0 +T1+ T2的结果，而T5的值是T1 +T2+ T3的结果，依次内推…
  
  算法原理
  
  在讲解此题的算法原理之前，我们先了解一下动态规划：
  [动态规划 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 dp(n+1);
        //初始化
        dp[0]=0;
        dp[1]=dp[2]=1;
        //填表：
        for(int i=3;i
            dp[i] = dp[i-1]+ dp[i-2] +dp[i-3];
        }
        //返回值：
        return dp[n];
    }
};
```