动态规划初入门

《动态规划初入门》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划初入门1．LCS问题描述：给定两个字符串a和b，请求出其最长公共子序列。(设a、b的长度分别是m、n)如：a="abcfb"  b="abfcab"  result="abcb"设状态c[I,j]表示a的前i个字符和b的前j个字符所求得的最长公共子序列长度设s[I,j]表示状态c[I,j]是由哪个状态转移的，0表示c[i-1,j-1]，1表示c[i-1,j]，2表示c[I,j-1]。则状态转移方程为：c[I,j]=0;                ifI=0orj=0  边界条件c[I,j]=c[I-1,j-1]+1;        ifI,j

2、>0anda[i]=b[j]  c[I,j]=max(c[I,j-1],c[i-1,j]);ifI,j>0anda[i]!=b[j]s[I,j]无意义ifI=0orj=0    s[I,j]=0  ifI,j>0anda[i]=b[j]s[I,j]=1;  ifI,j>0anda[i]!=b[j]andc[i-1,j]>c[i,j-1]s[I,j]=2;  ifI,j>0anda[i]!=b[j]andc[i,j-1]>c[i-1,j]当求出所有状态后c[m,n]就是最长序列的长度，而且我们可以从s[m,n]逆推出最长公共子序列。时间复杂度O(n^2)2

3、．石子合并问题描述：N堆石子排成一列。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。请你选择一种合并石子的方案，使得做N－1次合并，得分的总和最小。比如有4堆石子：    4  4  5  9则最佳合并方案如下：4  4  5  9  score:0              8  5  9    score:8                13  9      score:8+13=21                  22      score:8+13+22=43首先我们做一下预

4、处理，令w[I,j]表示第i堆到第j堆石子的石子总数，如w[0,3]=13。  w[I,i]=num[i]    w[I,j]=w[I,j-1]+num[j]    I

5、1  10  2    9    3    8    4    7    5    6其中最长上升序列长度为6，是：123456。算法1：我们令f[i]表示前i个数中找到的以第i个数num[i]结尾的最长链的长度。那么，很容易列出方程f[0]=0;f[i]=max(f[j]

6、j

7、1<=I<=N)上述算法的复杂度是O(N^2)，类似第一题，引入s[i]表示f[i]是由哪个状态转移过来的，则可逆推出最长升链。现在我们再看一下这个问题的一个变形：请你用最少的不上

8、升序列覆盖这N个数。上面的例子最少要用6条非升链覆盖：1234510  9    8    7    6再举一个例子(N=11)：100  8999897675928354901要用3条非升链：1008989767554199928390而我们再观察一下它的最长升链，其中一条是：758390，长度也为3！这是巧合还是必然？这是必然！！！可以证明非升链覆盖问题和最长升链问题是同解的。同样，升链覆盖、降链覆盖、非降链覆盖和最长非升链、最长非降链、最长降链同解。口诀：前面加“非”字~大家可以想象证明，等大家了解了算法2，就自然明白了。算法2：由于N的规模，算法

9、一是在太慢了。这里介绍一种O(nlogn)的算法。首先定义数组D：D[i]（1<=I<=N）表示目前为止，所有长度为i的升链中，最后一个元素的最小可能值。如当前找到两个长度为3的升链：234；139那么D[3]=4。显然，对于同样长度的升链，结尾越小越容易拓展成更长的升链。并且可知D是一个严格升链（若其中D[i+1]<=D[i]，则去i+1链中第i个元素赋给D[i]）我们还设置一个变量s表示目前为止找到最长链的长度。初始s=0,D赋正无穷。然后依次扫描数列中的每一个数。譬如现在扫到第i个数，首先在D中二分查找num[i]可以放置的位置p，满足D[p]>=

10、num[i]and(p=0orD[p–1]