动态规划(算法)---01.斐波那契数列模型_第N个泰波那契数

前言：

  有一个很著名的公式 “程序=数据结构+算法”。

  算法是模型分析的一组可行的，确定的，有穷的规则。通俗的说，算法也可以理解为一个解题步骤，有一些基本运算和规定的顺序构成。但是从计算机程序设计的角度看，算法由一系列求解问题的指令构成，能根据规范的输入，在有限的时间内获得有效的输出结果。算法代表了用系统的方法来描述解决问题的一种策略机制。

  完成同一件事的不同的算法完成的时间和占用的资源可能并不相同，这就牵扯到效率的问题。算法的基本任务是针对一个具体的问题，找到一个高效的处理方法，从而完成任务。而这就是我们的责任了。

 学习算法我这里先从动态规划开始，先以基础题目入手，逐渐增加难度，了解解决动态规划算法题的一个简单流程，先用简单几道题入门。

我们先以斐波那契数列模型_第N个泰波那契数这道题为例：https://leetcode.cn/problems/n-th-tribonacci-number/description/

一、题目解析

  这道题是斐波那契数列的加强版，具体改动在元素下标从0开始，这里稍微注意就好。并且从第四个数开始，每个数的值等于前三项元素的和，也就是Tn = Tn-3 + Tn-2 + Tn-1 

  题目要求我们返回Tn的值。

二、算法原理

1、状态表示

  我们在状态标识的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。 

  状态简单理解就是dp表内某一个值代表的含义。

如何确定状态表示

• 题目要求

简单的题目里一般会给出

• 经验+题目要求

越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。

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

  分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。

---

  那我们这道题的状态表示是什么呢？我们第一次学也可以看得出来，就是第n个泰波那契的值，所以，我们创建一个一维数组dp，让dp[0]的值代表第0个泰波那契数的值，dp[1]的值代表第1个泰波那契数的值，dp[n]的值代表第n个泰波那契数的值。dp[0]代表的是第0个泰波那契数的值原因是我们泰波那契数列下标是从0开始的。

  可知，状态表示为：dp[i]表示第i个泰波那契的值

  有了状态表示才有之后的对状态转移方程的推导，所以这一步最为重要！

2、状态转移方程

  确定状态表示之后我们就可以根据状态标识推出状态转移方程

  状态转移方程是什么？

不讲什么复杂的，简单来说状态转移方程就是    dp[i]等于什么 dp[i]=？

  这个就是状态转移方程，我们要做的，就是推出dp[i]等于什么

  我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步

  我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推

  这道题我们根据状态表示和题目，我们就可以知道dp[i]=dp[i-1]+dp[i-2]+dp[i-3],这就是我们的状态转移方程。

3、初始化

  我们创建dp表就是为了把他填满，我们初始化是为了防止在填表的过程中越界

  怎么谈越界？

  在这道题中，我们知道一个泰波那契数的值等于其前三个泰波那契的值的和，我们根据状态转移方程可知，dp[i]=dp[i-1]+dp[i-2]+dp[i-3] ，那当我们填dp[0]、dp[1]、dp[2]的时候，其实是存在越界的，所以我们为了防止越界，就要先去解决越界，由题可知，dp[0]、dp[1]、dp[2]的值我们已知，所以我们就可以先把这三个值填入dp表，这样在之后填表的时候就不会有越界问题发生，因为其前三个值都会存在！

把这三个值填入表中，解决越界问题，这个就叫dp表的初始化

4、填表顺序

  注意填表顺序，是因为我们需要在填当前状态的时候，所需要的状态已经计算过了

  这个意思就是，我们在填状态dp[3]的时候，我们就已经知道其所需要的dp[0]、dp[1]、dp[2]状态的值了， 那假如我们呢直接填dp[4]，可其所需要的状态dp[3]我们还没填，所以就计算不出来我们当前状态dp[4]的值，所以填表顺序也是需要考虑的一项

  这道题的填表顺序就是我们需要从状态dp[3]开始，依次填表。

5、返回值

  返回值就是我们最后需要求出的值，在这里也就是我们我们的dp[n]。返回值一般通过题目要求和状态表示来判断出来。

  以上就是我们算法原理的五步，这五步完成，其实我们就已经可以解题了。

三、编写代码

class Solution {
public:
    int tribonacci(int n) {
        //细节问题
        if(n==0) return 0;
        if(n==1||n==2) return 1;
       // 1、创建dp表
        vector<int>dp(n+1);
       // 2、初始化
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
      // 3、填表
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
       // 4、返回值
        return dp[n];
    }
};

 问题解释：

•   这里的细节问题是因为当n<3时，在填表部分会有越界问题发生，所以在此前面对其进行细节处理。
•   创建dp表时，将其大小设置为n+1,是因为泰波那契数下标是从0开始的。