决定总结回忆一下一些算法问题,先从最大子序列问题开始吧.
问题的描述如下:给定一个数列a(1..n),求其一连续子列其和最大,即max{sum{a(i..i+p)}}.
这道题材可以用DP(动态规划)解,时间复杂度为O(n),解法如下:
f(i):=以a(i)结尾的最大连续子列和
则我们有:f(i)=max{f(i-1),0}+a(i).(f(1)=a(1))
这很好理解,因为如果前面i-1个数,以i-1结尾的最大值为负值,我们就可以将其舍去.根据上式,我们可以算出所有的f(i),然后再扫描f(i),先出最大值就是答案.
我们来看一下一个和这个问题很相似的问题:
给定一个矩阵a(1..n,1..m),求其一子矩阵a(i..j,k..l)其和最大.
我们当然不想去扫描整个子矩阵空间,这样必然导致时间复杂度为O(n^4),由上题的提示,我们可以同样用DP,可以在O(n^3)内解决:
f(i,j,k):=以a(k,i..j)为最后一行的子矩阵的和
则我们有:f(i,j,k)=max{0,f(i,j,k-1)} + sum{a(k,i..j)} (f(i,j,0)=sum{a(0,i..j)})
同样扫描,f空间就可以了,这是一个n^3的.
另外一个有趣的问题是:
给定a(1..n),求最长上升子列的长度即满足a(b(0)..b(m)),其中b(i)<b(i+1),a(b(i))<a(b(i+1))
同样我们用DP搞定它,先是一个O(n^2)的算法
f(i):=以a(i)结尾的最大上升子列的长度.
f(i):=max{1,f(j)+1} (j=1..i-1,a(i)<a(j))(f(1)=1)
在这个基础上,有一个O(nlogn)的算法,考虑到f(j)(1..i-1),当f(x)=f(y)=k时,我们会选择a(x),a(y)中比较小的做为下一步递推的前缀,所以我们记下d(k)=min{a(i)}(f(i)=k),d(k)是不减的.这时我们可以用二分查找法在d中查找,找到那个满足d(k)<a(i),d(k+1)>=a(i)的值,则这就是我们的max{f(j)+1}.
DP有好多经典的例子,说到回忆,就不得不回忆一下大名鼎鼎的dijkstra算法.首先描述一下问题吧(单源最短路径)
G=<V,E,s>,G为连通图,E中的权全非负,s为源,求s到其它顶点的最短路径.
d(i,k):=前k个顶点构成的子图中,s到i的最短路径
d(i,k)= min{d(i,k-1),d(k)+e(k,i)}(d(i,0)=e(i,s))
另外一个很有名的问题是最长公共子串的问题:
char stra(1..n),strb(1..m),求满足
f(i,j):=str(1..i)和str(1..j)的最长公子串长度
f(i,j)= (stra(i)==strb(j))?max{f(i-1,j),f(i,j-1)}:f(i-1,j-1)+1 (f(i,0)=f(0,j)=0).
这里突然想到一个问题,最长公共连续子串的长度是否可以用DP来解决呢,小试一下:
f(i,j):=str(1..i),str(1..j)分别以stra(i),strb(j)结尾的连续公共子串
f(i,j):=f(i-1,j-1)+1 (stra(i)=strb(j)) or
f(i-1,j) or
f(i,j-1)(f(0,j)=f(i,0)=0)
时间复杂度O(nm),好像有点高,不知道有没有更好的算法.
DP可以说是千变万化,总结一下,当一个问题可以用子问题表示,且子问题有很大的重复,可以考虑用DP来解决.
| 网站地图 |