扔掉抽象难懂专业名词，带你从头开始理解入门动态规划1

注：并非指专业名词概念不好，而是认为乍一接触dp就开始啃那些难得名词比较容易劝退，这里用简单的思维理解来了解入门dp。

什么是动态规划（dp）？

1.动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

2.由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

例题

汗流浃背了嘛，哥们，没关系接下来结合例题带你走入dp

如何进行动态规划算法的实现？

首先创建一个dp表：

dp表？？？

dp表就是一个数组被命名为dp用来帮助我们进行动态规划的实现，存储分解的简单子问题的状态。

在这里这道题目中因为要求下一个泰波那契数需要前三个数据，所以我们将泰波那契的每一个数存储下来以用来后续使用

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

一般来说是通过上述五步来进行实现动态规划的算法，接下来我会通过简单易懂的非官方语言讲解五步。

1.状态表示

状态表示就是dp表内数据所蕴含的意义，以例题中dp表中的数据意义就是第x个泰波那契数

一般来说状态表示如何得到呢？

1.题目要求（题目直接给了）

2.经验+题目要求（多多的刷题）

3.分析题目的要求中发现的重复子问题（机灵的脑袋瓜分析）

2.状态转移方程

dp[i]该等于什么，或者说为dp[i]赋值的方式方法

该例题的状态转移方程就是前三个数据相加。

3.初始化

要通过对dp表初始化来保证使用方程填表时不越界，能运行的效果

例如本题的dp[0]dp[1]dp[2]三个数据是无法通过状态转移方程得到的，所以我们需要初始化这三个数据

4.填表顺序

我们要选择合适的填表顺序使得通过状态转移方程来填表时能够正常进行，填写当前状态时所需要的数据已经知道。

此题中毫无疑问，我们应该从dp[0]——>向dp[n]的方向移动顺序填表.

5.返回值

从dp表中的数据结合题目要求，返回一个恰当的值

此题中我们就恰好要返回dp[n]

例题代码实现（非最简最优，仅供参考）

class Solution {
public:
    int tribonacci(int n) {
        vector<int> dp={0,1,1};
        for(int i=3;i<=n;i++)
        {
            dp.push_back(dp[i-1]+dp[i-3]+dp[i-2]);
        }
        return dp[n];
    }
};

结尾

怎么样学会了嘛，点个赞是对我最大的鼓励。害怕自己忘记嘛，收藏一下吧，温故才能知新呢。

我会接下来发布更多有用易懂的知识包括但不限于动态规划相关，贪心算法相关等各式实用有用算法以及编程语言语法等知识，感兴趣请点个关注。