文前一唠：今天（4月18日）的洛谷日报是我的文章~（没有开玩笑，真的是我写的，不信你去看）

dp是什么？

dp就是一种将大问题拆分成数个子问题，用已知情况的最值，推出未知情况的最值的递推思想的算法，速度与爆搜相比，快到不知道哪里去（并非指数级增加），跟记忆化搜索的复杂度相比有时会相差一些常数。

动态规划常常适用于有重叠子问题和最优子结构性质的问题。本行改自维基百科

通常许多子问题完全相同，动态规划只会解决每个子问题一次然后用数组存储下来，从而减少计算量。这点与记忆化搜索有异曲同工之妙。

P1115 最大子段和

写$dp$时要考虑几个东西：状态（$f[i]$存什么东西），转移方程（怎么递推），答案（是$f[n]$？还是数组中每一项的最大值？），和初值（（大型爆炸现场→）~~memset(array,1,sizeof(array))~~数组的第几项设为什么值？）

首先，我们需要考虑数组中$f[i]​$存的是什么内容，要使其能递推出后面的项。（此处省略思考过程100字）