题目描述

给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A="1A2C3D4B56"，B="B1D23CA45B6A"，"123456"或者"12C4B6"都是最长公共子序列。给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。

求解过程

设给定的str1的长度为N,str2的长度为M.生成一个N*M的矩阵dpdp[i][j]的含义为,str1的 子串0-i与str2的自串0-j的最长公共子序列.对于矩阵第一行来说,即dp[0][i]来说,代表Str1[0]与str2[0-i]的最长公共子序列.若,str1[0]==str2[M],0<=M<=i则 M-I的值都为1.同理对于第一列也是如此.对于其他情况分以下三种情况讨论1.dp[i][j] = dp[i-1][j];    例如 A1BC2 AB34C  dp[3][4] = 3;dp[4][4]=32.dp[i][j] = dp[i][j-1];    例如AB34C A1BC23.dp[i][j] = dp[i-1][j-1];    这种情况的发生的前提为 str1[i] == str2[j];    例如 ABCD,ABCD综上所述,dp[i][j]的值为三者中最大的.

代码实现

class LCS {public:    int findLCS(string A, int n, string B, int m)     {        vector
   
    
      >dp(n, vector
     
      (m, 0));        bool flag = false;        for (int i=0;i

转载地址：http://eehji.baihongyu.com/

你可能感兴趣的文章

企业如何运用企业云盘进行数字化转型-实现新发展