和小哥哥一起刷洛谷(13)【未完】

一维dp

Posted by ethan-zhou on April 18, 2019

文前一唠:今天(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
本文为作者原创,转载请注明出处:本文链接