dp相信大家都听过吧，但大部分菜鸟（包括我自己）都还不懂dp是个啥玩意，所以今天，我就来给大家讲一下dp。

一，什么是dp

dp，就是动态规划，一般来说，就是用一个数组把当前数据最优的答案记录下来的算法

举个例子，y总讲的背包你们看过吧，背包其实也是一种dp,f[i]就是重量为i的最优答案

所以......dp就是差不多这个样子

dp缺点：耗时间耗空间
dp优点：适用性大，大多数问题都可以用dp，并且dp也比较好打

二，dp用法

首先要先定义一个数组，1维的够了，因为大部分dp都可以简化成1维数组

int f[105];

然后分析以下问题
1,f[i]中是什么数值
2,f[i]可能是什么数值
3,在f[i]可能的数值中,我们到底需要哪个
4,在f数组中,哪个才是我们需要的值

就以01背包为例子吧：
第1个问题:f[i]是重量为i的最优解
第2个问题:f[i]可能是f[j-v]+w(选择),或者不变(不选)
第3个问题:对于每个f[i]，我们需要最大的那个(感觉本人在说废话)
第4个问题:最终答案是f[V]

时间复杂度:O(N*V)

既然你分析完了，就可以愉快写代码了

三，dp方法

1，分析f数组的每个维度代表什么
2，思考f数组每个成员有哪些可能的量
3，把每个f数组成员赋值
4，输出我们需要的答案