算法修炼-动态规划之斐波那契数列模型

一、动态规划的算法原理

��       这是本人动态规划的第一篇文章，所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表（一段数组）。首先要先确定好dp表每个位置的值所代表的含义是什么，然后通过题目条件以及经验推出状态转移方程，第三个就是初始化，确定填表顺序以及保证填表不越界，最后输出题目所需的结果，大致就是这个思路。

二、斐波那契数列模型例题分析

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

本题的思路较为简单，状态转移方程已经给出，直接上代码：

class Solution {public:    int tribonacci(int n)     {        vector v1(n+1);        //初始化        if(n == 1)        return 1;        else if(n == 2)        return 1;        else if(n == 0)        return 0;        v1[0] = 0;        v1[1] = 1;        v1[2] = 1;                for(int i = 3; i