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