全部博文（37）
分类： C/C++
2008-07-03 16:27:36
问题描述：给定两个字符串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; if I = 0 or j = 0 边界条件
c[I,j] = c[I-1,j-1] + 1; if I, j > 0 and a[i] = b[j]
c[I,j] = max(c[I, j-1], c[i-1, j]); if I, j >0 and a[i] != b[j]
s[I,j] 无意义 if I = 0 or j = 0
s[I,j] = 0 if I, j > 0 and a[i] = b[j]
s[I,j] = 1;if I, j > 0 and a[i] != b[j] and c[i-1,j] > c[i,j-1]
s[I,j] = 2;if I, j > 0 and a[i] != b[j] and c[i,j-1] > c[i-1,j]
当求出所有状态后c[m,n]就是最长序列的长度，而且我们可以从s[m,n]逆推出最长公共子序列。时间复杂度O(n^2)
2．石子合并
问题描述：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首先我们做一下预处理，令w[I,j]表示第i堆到第j堆石子的石子总数，
如w[0,2]=13。 w[I, i] = num[i]
w[I, j] = w[I, j-1] + num[j] I < j
我们定义状态f[I, j]表示将第i堆至第j堆石子合并到一起的总得分，自然有：
f[I, j] = 0 if I = j
f[I, j] = min(f[I, k] + f[k + 1, j] && I <= k < j) + w[I, j] if I < j
则f[0, n-1]则是最后答案，时间复杂度O(n^3)。
3．最长上升序列
问题描述：给定N（N <= 1000000）个数，请在其中找出最长的一个上升链（严格上升）。
例：1 10 2 9 3 8 4 7 5 6
其中最长上升序列长度为6，是：1 2 3 4 5 6。
算法1：
我们令f[i]表示前i个数中找到的以第i个数num[i]结尾的最长链的长度。那么，很容易列出方程
f[0] = 0;
f[i] = max(f[j] | j < I and num[j] < num[i]) + 1 1 <= I <= N
最后结果是：ans = max(f[i] | 1 <= I <= N)
上述算法的复杂度是O(N^2)，类似第一题，引入s[i]表示f[i]是由哪个状态转移过来的，则可逆推出最长升链。
现在我们再看一下这个问题的一个变形：请你用最少的不上升序列覆盖这N个数。
上面的例子最少要用6条非升链覆盖：
1
2
3
4
5
10 9 8 7 6
再举一个例子(N = 11)：100 89 99 89 76 75 92 83 54 90 1
要用3条非升链：
100 89 89 76 75 54 1
99 92 83
90
而我们再观察一下它的最长升链，其中一条是：75 83 90，长度也为3！
这是巧合还是必然？
这是必然！！！可以证明非升链覆盖问题和最长升链问题是同解的。同样，升链覆盖、降链覆盖、非降链覆盖和最长非升链、最长非降链、最长降链同解。
口诀：前面加“非”字~
大家可以想象证明，等大家了解了算法2，就自然明白了。
算法2：
由于N的规模，算法一是在太慢了。这里介绍一种O(nlogn)的算法。
首先定义数组D：D[i]（1 <= I <= N）表示目前为止，所有长度为i的升链中，最后一个元素的最小可能值。如当前找到两个长度为3的升链：2 3 4；1 3 9 那么D[3] = 4。显然，对于同样长度的升链，结尾越小越容易拓展成更长的升链。并且可知D是一个严格升链（反证：若其中D[i+1] <= D[i]，则在i+1链中的第i个元素肯定要小于D[i]，将其赋给D[i]）
我们还设置一个变量s表示目前为止找到最长链的长度。初始s=0, D赋正无穷。
然后依次扫描数列中的每一个数。譬如现在扫到第i个数，首先在D中二分查找num[i]可以放置的位置p(查找范围是[1,s])，满足D[p] >= num[i] and (p = 0 or D[p – 1] < num[i])。将num[i]写入D[p]，如果p>s(p=s+1)，说明找到更长的链，更新s(s++)。
例如：1 3 2 5 4 5
initial s = 0
step1 s = 1 D[1] = 1
step2 s = 2 D[1] = 1 D[2] = 3
step3 s = 2 D[1] = 1 D[2] = 2
step4 s = 3 D[1] = 1 D[2] = 2 D[3] = 5
step5 s = 3 D[1] = 1 D[2] = 2 D[3] = 4
step6 s = 4 D[1] = 1 D[2] = 2 D[3] = 4 D[4] = 5
显然这个算法是O(nlogn)的。
同样这个算法证明了前面讨论的变形的正确性。首先，本算法实际上构造出了用最长升链长度（MAXL）条非升链覆盖这N个数的一组解（这组解是这样构造的：当发现有D[p]>=num[i]时，将num[i]写入D[p]，此时原D[p]值与当前num[i]就构造了一条非升链的一部分，看上例分析可知，解为1/3 2/5 4/5）.我们只需要证明至少要用MAXL条非升链才能完成覆盖即可，显然，最长升链就需要MAXL条降链覆盖。（最长升链的长度为s，而这s个数必须要分布在不同的s条非升链来覆盖，因为它们不可能出现在同一条非升链中，对不对？所以s是非升链覆盖的下界，例如1 3 2 5 4 5的最短非升链覆盖问题条数为4，分别为1/3 2/5 4/5）证毕.
