文前一唠：今天（4月18日）的洛谷日报是我的文章~（没有开玩笑，真的是我写的，不信你去看）
dp是什么？
dp就是一种将大问题拆分成数个子问题，用已知情况的最值，推出未知情况的最值的递推思想的算法，速度与爆搜相比，快到不知道哪里去（并非指数级增加），跟记忆化搜索的复杂度相比有时会相差一些常数。
动态规划常常适用于有重叠子问题和最优子结构性质的问题。本行改自维基百科
通常许多子问题完全相同，动态规划只会解决每个子问题一次然后用数组存储下来，从而减少计算量。这点与记忆化搜索有异曲同工之妙。
P1115 最大子段和
写\(dp\)时要考虑几个东西：状态（\(f[i]\)存什么东西），转移方程（怎么递推），答案（是\(f[n]\)？还是数组中每一项的最大值？），和初值（（大型爆炸现场→）memset(array,1,sizeof(array))
首先，我们需要考虑数组中\(f[i]\)存的是什么内容，要使其能递推出后面的项。（此处省略思考过程100字）
| 状态 | 转移方程 | 答案 | 初值 |
|---|---|---|---|
| 包括第i个数且最大的字段和 | \(f[i]=max(f[i-1]+arr[i],arr[i])\) | \(f[i]，i\in[1,n]中的最大值\) | 数组的每一项都为零 |
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: