河南省住房和城乡建设厅网站查证,软件网站是怎么做的吗,网站注册登录页面设计,如何给网站做右侧导航栏一#xff0c;问题描述给定两个字符串#xff0c;求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1#xff1a;BDCABA#xff1b;字符串2#xff1a;ABCBDAB则这两个字符串的最长公共子序列长度为4#xff0c;最长公共子序列是#xff1a;BCBA二…一问题描述给定两个字符串求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1BDCABA字符串2ABCBDAB则这两个字符串的最长公共子序列长度为4最长公共子序列是BCBA二算法求解这是一个动态规划的题目。对于可用动态规划求解的问题一般有两个特征①最优子结构②重叠子问题①最优子结构设 X(x1,x2,.....xn) 和 Y{y1,y2,.....ym} 是两个序列将 X 和 Y 的最长公共子序列记为LCS(X,Y)找出LCS(X,Y)就是一个最优化问题。因为我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS首先考虑X的最后一个元素和Y的最后一个元素。1)如果 xnym即X的最后一个元素与Y的最后一个元素相同这说明该元素一定位于公共子序列中。因此现在只需要找LCS(Xn-1Ym-1)LCS(Xn-1Ym-1)就是原问题的一个子问题。为什么叫子问题因为它的规模比原问题小。(小一个元素也是小嘛....)为什么是最优的子问题因为我们要找的是Xn-1和 Ym-1 的最长公共子序列啊。。。最长的换句话说就是最优的那个。(这里的最优就是最长的意思)2)如果xn ! ym这下要麻烦一点因为它产生了两个子问题LCS(Xn-1Ym) 和 LCS(XnYm-1)因为序列X 和 序列Y 的最后一个元素不相等嘛那说明最后一个元素不可能是最长公共子序列中的元素嘛。(都不相等了怎么公共嘛)。LCS(Xn-1Ym)表示最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。LCS(XnYm-1)表示最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。求解上面两个子问题得到的公共子序列谁最长那谁就是 LCS(X,Y)。用数学表示就是LCSmax{LCS(Xn-1Ym)LCS(XnYm-1)}由于条件 1) 和 2) 考虑到了所有可能的情况。因此我们成功地把原问题 转化 成了 三个规模更小的子问题。②重叠子问题重叠子问题是啥就是说原问题 转化 成子问题后 子问题中有相同的问题。咦我怎么没有发现上面的三个子问题中有相同的啊OK来看看原问题是LCS(X,Y)。子问题有 ❶LCS(Xn-1Ym-1) ❷LCS(Xn-1Ym) ❸LCS(XnYm-1)初一看这三个子问题是不重叠的。可本质上它们是重叠的因为它们只重叠了一大部分。举例第二个子问题LCS(Xn-1Ym) 就包含了问题❶LCS(Xn-1Ym-1)为什么因为当Xn-1 和 Ym 的最后一个元素不相同时我们又需要将LCS(Xn-1Ym)进行分解分解成LCS(Xn-1Ym-1) 和 LCS(Xn-2Ym)也就是说在子问题的继续分解中有些问题是重叠的。由于像LCS这样的问题它具有重叠子问题的性质因此用递归来求解就太不划算了。因为采用递归它重复地求解了子问题啊。而且注意哦所有子问题加起来的个数 可是指数级的哦。。。。这篇文章中就演示了一个递归求解重叠子问题的示例。那么问题来了你说用递归求解有指数级个子问题故时间复杂度是指数级。这指数级个子问题难道用了动态规划就变成多项式时间了呵呵哒。。。。关键是采用动态规划时并不需要去一 一 计算那些重叠了的子问题。或者说用了动态规划之后有些子问题 是通过 “查表“ 直接得到的而不是重新又计算一遍得到的。废话少说举个例子吧比如求Fib数列。关于Fib数列可参考求fib(5)分解成了两个子问题fib(4) 和 fib(3)求解fib(4) 和 fib(3)时又分解了一系列的小问题....从图中可以看出根的左右子树fib(4) 和 fib(3)下是有很多重叠的比如对于 fib(2)它就一共出现了三次。如果用递归来求解fib(2)就会被计算三次而用DP(Dynamic Programming)动态规划则fib(2)只会计算一次其他两次则是通过”查表“直接求得。而且更关键的是查找求得该问题的解之后就不需要再继续去分解该问题了。而对于递归是不断地将问题分解直到分解为 基准问题(fib(1) 或者 fib(0))说了这么多还是要写下最长公共子序列的递归式才完整。借用网友的一张图吧)c[i,j]表示(x1,x2....xi) 和 (y1,y2...yj) 的最长公共子序列的长度。(是长度哦就是一个整数嘛)。公式的具体解释可参考《算法导论》动态规划章节三LCS python实现1 defLCS(str1, str2):2 c [[0 for i in range(len(str2)1)] for j in range(len(str1)1)]3 for i in range(1, len(str1)1):4 for j in range(1, len(str2)1):5 if str1[i-1] str2[j-1]:6 c[i][j] c[i-1][j-1] 17 else:8 c[i][j] max(c[i][j-1], c[i-1][j])9 printc10 return c[-1][-1]1112 if __name__ __main__:13 str1 BDCABA14 str2 ABCBDAB15 print LCS(str1, str2)感觉整个代码就是直接根据上面的那个递归表达式写的。①第1行定义一个数组来保存最长公共子序列的长度②第78行就是递归表达式的程序表示。就是 c[i,j] max{c[i][j-1], c[i-1][j]}③第10行返回最终结果。
