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\)结束的最大子段和
则递归剖析即可
int f(int x){
if(x==1){//边界条件
return a[1];
}
return max(f(x-1)+a[x],a[x]);//求最大值
、}
这样时刻很慢，原因是存在许多现已算过的节点被重复核算
所以用一个\(val\)记载核算过的节点信息
for(int i=1;i<=n;i++){
dp[i]=inf;
}
int f(int x){
if(dp[x]!=inf){
return dp[x];//现已记载过的节点信息
}
if(x==1){//边界条件
return a[1];
}
dp[x]=max(f(x-1)+a[x],a[x]);//求最大值
return dp[x];
}
上述优化办法即回忆化查找，是一种根本DP办法
回忆化查找是一种经过记载现已遍历过的状况的信息，然后防止对同一状况重复遍历的查找完成办法。 ------OI Wiki
转成递推方式就成了根本的线性DP
dp[1]=a[1];
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-1]+a[i],a[i]);
maxi=max(maxi,dp[i]);
}
例.2-最长上升子序列(LIS)
剖析
DP四步
⑴界说状况
界说\(dp_i\)表明以\(i\)结束的最长上升子序列长度
⑵剖析答案
答案即\({\max}^{i\in[1,n]}_{dp_i}\)
⑶剖析方程
关于每个\(i\)，有若干\(j<i\)且\(a_j<a_i\)：
- 能够与每一个\(j\)的最长上升子序列拼接，组成新的子序列长度\((dp_{j}+1)\)
- 能够自己独自成一个子段和\(1\)
求\(\max\)
⑷边界条件
即\(dp_i\)为\(1\)，由于每个\(dp\)值至少为\(1\)
代码完成
运用递推，枚举\(i\),而且枚举\(j(j<i)\)
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[j]+1,dp[i]);
}
}
maxi=max(maxi,dp[i]);
}
重点题-导弹阻拦
50分做法
第一小问即求最长不上升子序列长度
第二问能够用Dilworth 定理处理
把序列分红不上升子序列的最少个数，等于序列的最长上升子序列长度。把序列分红不降子序列的最少个数，等于序列的最长下降子序列长度。
所以第二问等价于求最长上升子序列长度
100分做法
运用贪心优化假如，假如一个方位能够有\(2,3\)两个数选一个数，咱们必定会选\(2\)，由于选2后边就有更多的时机拼接。
界说一个\(c\)数组存贮现已选了的数
只需每次二分查找第一个能够等价替换的数，就能将其替换，在过程中记载DP即可。
详细代码
弥补
DP的要素：
- 数据规模较小
- 能够拆解为多个子问题
