<object id="getjk"></object>
<object id="getjk"></object>
    1. <object id="getjk"></object>
    2. <th id="getjk"></th>
      XYcooper
      • 性别: Icon_minigender_1
      • 博发娱乐城送钱

      ▯□☐Lintcode77 Longest Common Subsequence solution 题解◘

       

      阅读更多
      □☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□
      本帖最后由 742510994 于 2017-11-23 00:05 编辑

      【题目描述】
      Given two strings, find the longest common subsequence (LCS).
      Your code should return the length ofLCS.
      给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。

      【题目链接】
      www.lintcode.com/en/problem/longest-common-subsequence/

      【题目解析】
      求最长公共子序列的数目,注意这里的子序列可以不是连续序列,务必问清楚题意。求『最长』类的题目往往与动态规划有点关系,这里是两个字符串,故应为双序列动态规划。
      这道题的状态很容易找,不妨先试试以f[j]表示字符串A 的前i位和字符串 B 的前j位的最长公共子序列数目,那么接下来试试寻找其状态转移方程。从实际例子ABCD和EDCA出发,首先初始化f的长度为字符串长度加1,那么有f[0][0] = 0,f[0] = 0,f[0] = 0, 最后应该返回f[lenA][lenB]. 即 f 中索引与字符串索引对应(字符串索引从1开始算起),那么在A 的第一个字符与 B 的第一个字符相等时,f[1][1] = 1 + f[0][0], 否则f[1][1] = max(f[0][1], f[1][0])。
      推而广之,也就意味着若A == B[j], 则分别去掉这两个字符后,原 LCS 数目减一,那为什么一定是1而不是0或者2呢?因为不管公共子序列是以哪个字符结尾,在A == B[j]时LCS 最多只能增加1. 而在A != B[j]时,由于A或者B[j]不可能同时出现在最终的 LCS 中,故这个问题可进一步缩小,f[j] = max(f[i - 1][j], f[j - 1]). 需要注意的是这种状态转移方程只依赖最终的 LCS 数目,而不依赖于公共子序列到底是以第几个索引结束。
      【参考答案】
      www.jiuzhang.com/solutions/longest-common-subsequence/






      (责任编辑:XYcooper)
      分享到: