DP学习总结
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 -----OI Wiki例.1-最大子段和
分析
DP四步
⑴定义状态
定义\(dp_i\)表示以\(i\)结尾的最大子段和
⑵分析答案
答案即\({\max}^{i\in}_{dp_i}\)
⑶分析方程
对于每个\(i\)：
[*]可以与\(\)的最大子段和拼接，组成新的子段和\((dp_{i-1}+a_i)\)
[*]可以自己单独成一个子段和\(a_i\)
求\(\max\)
⑷边界条件
即\(dp_1\)为\(a_1\)
代码实现
递归写法
定义\(f(i)\)为以\(i\)结尾的最大子段和
则递归分析即可
int f(int x){
if(x==1){//边界条件
return a;
}
return max(f(x-1)+a,a);//求最大值
、}这样时间很慢，原因是存在许多已经算过的节点被重复计算
所以用一个\(val\)记录计算过的节点信息
for(int i=1;i 谢谢分享，试用一下 不错，里面软件多更新就更好了 yyds。多谢分享 不错，里面软件多更新就更好了 感谢分享，学习下。 感谢分享 感谢分享，学习下。 热心回复！ 鼓励转贴优秀软件安全工具和文档！ 感谢分享 yyds。多谢分享 感谢，下载保存了 鼓励转贴优秀软件安全工具和文档！ 感谢分享，下载保存了，貌似很强大 感谢发布原创作品，程序园因你更精彩 谢谢楼主提供！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢，下载保存了 感谢分享
页:
[1]
2