DP学习总结

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。    -----OI Wiki

例.1-最大子段和

分析

DP四步
⑴定义状态

定义\(dp_i\)表示以\(i\)结尾的最大子段和
⑵分析答案

答案即\({\max}^{i\in[1,n]}_{dp_i}\)
⑶分析方程

对于每个\(i\)：

• 可以与\([1,i-1]\)的最大子段和拼接，组成新的子段和\((dp_{i-1}+a_i)\)
  
• 可以自己单独成一个子段和\(a_i\)
  

求\(\max\)
⑷边界条件

即\(dp_1\)为\(a_1\)
代码实现

递归写法

定义\(f(i)\)为以\(i\)结尾的最大子段和
则递归分析即可

1. int f(int x){
2.         if(x==1){//边界条件
3.                 return a[1];
4.         }
5.         return max(f(x-1)+a[x],a[x]);//求最大值
6. 、}

复制代码

这样时间很慢，原因是存在许多已经算过的节点被重复计算
所以用一个\(val\)记录计算过的节点信息
[code]for(int i=1;i