动态规划初入门.doc

动态规划初入门1LCS问题描述：给定两个字符串a和b，请求出其最长公共子序列。(设a、b的长度分别是m、n)如：a = abcfbb = abfcabresult = abcb设状态cI, j表示a的前i个字符和b的前j个字符所求得的最长公共子序列长度设sI,j表示状态cI,j是由哪个状态转移的，0表示ci-1,j-1，1表示ci-1,j，2表示cI,j-1。则状态转移方程为：cI,j = 0; if I = 0 or j = 0边界条件cI,j = cI-1,j-1 + 1; if I, j 0 and ai = bj cI,j = max(cI, j-1, ci-1, j); if I, j 0 and ai != bjsI,j 无意义 if I = 0 or j = 0 sI,j = 0 if I, j 0 and ai = bjsI,j = 1; if I, j 0 and ai != bj and ci-1,j ci,j-1sI,j = 2; if I, j 0 and ai != bj and ci,j-1 ci-1,j当求出所有状态后cm,n就是最长序列的长度，而且我们可以从sm,n逆推出最长公共子序列。时间复杂度O(n2)2石子合并问题描述：N堆石子排成一列。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。请你选择一种合并石子的方案，使得做N1次合并，得分的总和最小。比如有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首先我们做一下预处理，令wI,j表示第i堆到第j堆石子的石子总数，如w0,3=13。 wI, i = numi wI, j = wI, j-1 + numj I j我们定义状态fI, j表示将第i堆至第j堆石子合并到一起的总得分，自然有：fI, j = 0 if I = jfI, j = min(fI, k + fk + 1, j & I = k j) + wI, j if I j则f0, n-1则是最后答案，时间复杂度O(n3)。3最长上升序列 问题描述：给定N（N = 1000000）个数，请在其中找出最长的一个上升链（严格上升）。例：1 10 2 9 3 8 4 7 5 6其中最长上升序列长度为6，是：1 2 3 4 5 6。算法1：我们令fi表示前i个数中找到的以第i个数numi结尾的最长链的长度。那么，很容易列出方程f0 = 0;fi = max(fj | j I and numj numi) + 1(1 = I = N)最后结果是：ans = max(fi | 1 = I = N)上述算法的复杂度是O(N2)，类似第一题，引入si表示fi是由哪个状态转移过来的，则可逆推出最长升链。现在我们再看一下这个问题的一个变形：请你用最少的不上升序列覆盖这N个数。上面的例子最少要用6条非升链覆盖：1 2 34510 9 8 7 6再举一个例子(N = 11)：10089 99 89 76 75 92 83 54 90 1要用3条非升链：100 89 89 76 75 54 199 92 8390而我们再观察一下它的最长升链，其中一条是：75 83 90，长度也为3！这是巧合还是必然？这是必然！可以证明非升链覆盖问题和最长升链问题是同解的。同样，升链覆盖、降链覆盖、非降链覆盖和最长非升链、最长非降链、最长降链同解。口诀：前面加“非”字大家可以想象证明，等大家了解了算法2，就自然明白了。算法2：由于N的规模，算法一是在太慢了。这里介绍一种O(nlogn)的算法。首先定义数组D：Di（1 = I = N）表示目前为止，所有长度为i的升链中，最后一个元素的最小可能值。如当前找到两个长度为3的升链：2 3 4；1 3 9 那么D3 = 4。显然，对于同样长度的升链，结尾越小越容易拓展成更长的升链。并且可知D是一个严格升链（若其中Di+1 = numi and (p = 0 or Dp 1 s，说明找到更长的链，更新s。例如：1 3 2 5 4 5initial s = 0 step1 s = 1 D1 = 1step2 s = 2 D1 = 1 D2 = 3step3 s = 2 D1 = 1 D2 = 2step4 s = 3 D1 = 1 D2 = 2 D3 = 5step5 s = 3 D1 = 1 D2 = 2 D3 = 4step6 s = 4 D1 = 1 D2 = 2 D3 = 4 D4 = 5显然这个算法是O(nlogn)的。同样这个算法证明了