【算法ACM DP】(转载)
DP是ACM算法中最重要的，主题类型千变万化，主题难度也很大。 技巧娴熟的算法，代码实现比较容易，1y率非常高。 总之DP总是重要的，是非常博大精深的算法。 我校Roba的lhzdhy在这方面有很深的造诣。
这几天，说起自己接触过的初级DP，DP中最重要的往往是状态与状态之间的转换。 如果找到状态转移方程式，递归地或递归地排列方程式，问题也会得到解决，但所谓难题，往往是第一次看也不知道，找不到状态转移方程式，或者甚至不知道状态是什么。 试分析一下关于DP的非常经典的三个问题。
.求局部最大和
宗旨是这样给出数组，在其中取任意连续的多个，使其和最大化。假设这个数组的大小为10，一般会想该怎么办，但一个连续的数组，必须在一个st和end中唯一
以下内容是程序代码：
for(ST=0； stn； st ) for(end=ST； endn； end ) for(I=ST； i=end； I ) max=n[i]；
一个三重环路，时间为10^3，可以不改变算法思想进行优化吗？ 答案是肯定的。
创建sum[10]数组时，表示来自数组n的累加。 这样，每次计算max时，只需操作一次sum[end]-sum[st-1]。 对于sum数组的创建过程，o[n]只需要一次时间，因此总时间复杂度将降低到o(10^2)。 能把复杂度调到O(N )吗？ 此时，使用动态规划的想法。 假设当前状态是以end结尾的局部最大和。 由此能否得到以end 1结尾的局部最大和。 想想看。 以end 1结束的话，可以分为两个部分。 一个是只有end 1这个要素，另一个是加上以end结尾的局部最大和，一般来说，从之前的状态中创造出最好的状态，具体的状态
以下内容是程序代码：
if(ans[I]0) ans[i 1]=n[i 1]； else ans[i 1]=ans[i] n[i 1]；
-top:0px; padding-bottom:0px; color:rgb(69,69,69); font-family:tahoma,helvetica,arial; font-size:13.63636302947998px; line-height:19.09090805053711px">再把遍历所有的ans，找出最大的就OK了，这样的话只需要Ｏ（n）的时间就能完成．
TOJ1782有道类似的题目，感兴趣的同学可以去看看．
２.最长递增子序列
大意是在一个序列中找到一个最长的递增子序列，求出其长度．例如1 7 3 5 9 4 8 Ans: 4 (1 -> 3 -> 5 -> 8)，咋看之下，好象没有合适的做法．遍历？２^n的复杂度，显然是不可行的．通过上面例题，我们可以考虑用DP的方法来解决这类问题．假设一个长度为n的数组，现在已经知道以从1到i为序列的尾的最大递增子序列，那么要求以i+1为尾的序列的最大递增子序列，只要判断n[i+1]是否大于a[1:i],然后取其中ans［i]最大的那个加１就是按ans[i+1]的值．最后在遍历所有的ans找出最大的即可．是不是和局部最大和很想象，唯一的不同就在于在局部最大和中只需要ans[i]即可求出ans[i+1],这是因为n[i+1]的前面只能接n[i]导致的，而这题的ans[i+1]确是由ans[1:i]共同决定的，这是由于最长递增子序列可以不连续导致的．换句话说，要是这题是求最长递增连续子序列的话，那就和上题的处理几乎一样了．说到这里，相信大家对DP都有了一个基本的了解了，我的理解是对于有些不知如何下手的题目，确定一个先前状态往往是给了一个已知条件，是问题明朗化了，再找到当前状态，所以说DP的难点在于状态划分和确定状态转移方程，而我的感觉是往往前者更重要．回到刚才那个题目，内层循环要做的是找到一个小于n[i+1]的并且长度最长的子序列，既然是查找，那能否找到Ｏ（logn）查找复杂度呢．答案是肯定的．具体怎么实现，大家可以查看这个网址:最长递增子序列的高效算法．上面说的很详细，我也理解的不好．
第三个问题下次再说吧，睡觉去了...
接着上次的内容,第三个经典例题:最长公共子串;
大意是:有两个字符串A,B,另有一字符串C,若C同时是A,B的子串,则C为公共子串,求出长度最长的公共子串的长度.
分析一下(2),(3),对于(2),如果A[i]==B[j],显然ans[i][j]要加1,那么会不会加2呢?如果加2的话,那么说明A[i],B[j]分别为公共子串两个不同的字符,那么必然有前后之分,前面的那个字符已经对应了一个字符串的尾部,另外一个字符则不可能是公共子串了,所以对于A[i]==B[j],ans[i][j]加且仅加1.对于(3)采取同样的分析,易知其分别减去A,B尾部的字符,必有一长度不变.
具体的代码实现可以有两种方式.
1.采取递推的实现方式,自底向上采取两重循环,时间复杂度为O(n^2),不过不是所有的状态转移方程都可以这样做,后面会详细分析.
2.自顶向下,逐级递归,但要注意递归层数(据说不能超过7600层),一般情况下都伴随这记忆化,这样能使时间复杂度从指数级别降低到O(n^2)的级别.至于和递推在时间上的优劣关 系,或者说有没有题用其中一种会TLE而另一种会AC,就不清楚了,望达人指教.
总结一下这三道经典例题.虽然是属于入门级的简单DP,但还是能给我们一点启示的.如何划分状态?有些时候,状态的划分不能仅仅根据答案,还应该加上某些限制条件,这样的话会更有利于状态的转移.像求局部最大和中ans[i]并不是前i个数列中的局部最大和值,还加上了该局部最大和的尾部必须是n[i],最长递增子序列也是一样.还有一点是状态的转移条件,有些时候只有一个前驱,而有的时候又有多个前驱,像2.(这也是2.的复杂度要比1.高的原因),这个要注意.关于这3道题,还有许多的类似问题,像多维局部最大和,最大m子段和等等.TOJ1564,POJ2479,TOJ1633都是相应的题目,感兴趣的同学可以做一下.回到刚才所说的,什么时候能用递推,什么时候又不能呢?
先看一下下面这道例题,POJ1088
大意是:给一个M*N的矩阵,每一点附上一个值h,要求求一条路径,路径上的相邻两点必须在矩阵中前后左右相邻,并且前驱的h值高于后继.很容易想到状态转移方程:l[i][j]=Max(l[i][j+1],l[i][j-1],l[i+1][j],l[i-1][j])+1//if(h[i][j+1]>h[i][j]...),那么用递归写的话只需
if(map[i][j]>map[i][j+1])if(flag[i][j+1]==-1) a=flag[i][j+1]=search(i,j+1);else a=flag[i][j+1];if(map[i][j]>map[i][j-1])if(flag[i][j-1]==-1) b=flag[i][j-1]=search(i,j-1);else b=flag[i][j-1];if(map[i][j]>map[i+1][j])if(flag[i+1][j]==-1) c=flag[i+1][j]=search(i+1,j);else c=flag[i+1][j];if(map[i][j]>map[i-1][j])if(flag[i-1][j]==-1) d=flag[i-1][j]=search(i-1,j);else d=flag[i-1][j];return Max(a,b,c,d)+1;
要是用递推怎么写呢,好象不好写吧,结合前面的3个例题(都是用递推写的),可以得出满足写递推式的两个条件:1.起点必须确定,象3.中ans[i][j]=0//if(i==0||j==0)是现而易见的,而此题在不同的输入下结果是不同的.2.每一点在推出时都能确保其前驱已被推出,在3.中,在二重循环中,明显在计算ans[i][j]中ans[i-1][j],ans[i][j-1],ans[i-1][j-1]已经确定了,但是此题却不能保证.
好了,说了这么多,相信大家对DP都有一个大致的印象了,划分好状态,找出状态转移方程,看能否用递推,不能的话就递归,但记住要记忆化哦.但是有一类题,和DP很像,但却很难找到转移方程,或者说起状态转移方程只不过是一个遍历的过程.对于这种题只要不和DP弄混,还是很好做的.
ZOJ1687大意是:一堆石头m个.两队人轮流取石头,每人取的上限都给出,至少要取一个,谁最后取完谁就失败,要你判断哪队能赢,咋看之下,确实没有状态转移,其实根本不用这么复杂,对于第i个人还剩下j块石头直接
for (i=1;i<=a[p];i++)if (tot - i > 0 && solve(tot-i,next) == 0){ ans[tot][p] = 1; return 1; //如果取子后对方会输，则返回1}
完全是暴力嘛,就这么简单!时间复杂度为O(石头数*人数),对于n队,应该也有同样的做法.
上面介绍的都是一些简单的DP和类DP的记忆化搜索,虽然简单,但十分基础.下面介绍另外一类比较常见的DP题(今天的contest就考上了,结果还看错了题,郁闷!!!)
雄心铁胆打天下，拼搏生命笑对天。
大肚能容天下辱，站稳脚跟学做人！