最长公共子序列(DP)-蒲公英云

最长公共子序列(DP)

た入场券 2022-06-10 11:41 299阅读 0赞

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
比如字符串1：BDCABA；字符串2：ABCBDAB

则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

思路： 1.分解子问题，由空串与空串最长公共子序列的问题递推到两个字符串的最长公共子序列
2.从空串开始保存每一个最长公共子序列，为下一个比自己大的字符串服务

递推公式：

= 0； 当i或j = 0 空串
maxLen[i][j] = maxLen[i-1][j-1] + 1;   当sz1[i-1] == sz2[j - 1]   字符相对
 = max(maxLen[i][j-1] , 
 maxLen[i-1][j]); 当sz1[i-1] ！= sz2[j - 1] 字符不相对，则为i-1或j-1中最大的

递推过程：

SouthEast

#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main() {
    while (cin >> sz1 >> sz2) {
        int length1 = strlen(sz1);
        int length2 = strlen(sz2);
        int nTmp;
        int i, j;
        //初始化边界，空串为0 i=0时 或 j=0时
        for ( i = 0; i <= length1; i++) 
            maxLen[i][0] = 0;
        for ( j = 0; j <= length2; j++)
            maxLen[0][j] = 0;
        for (i = 1; i <= length1; i++) {
            for (j = 1; j <= length2; j++) {
                if (sz1[i-1] == sz2[j - 1])
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                else
                    maxLen[i][j] = max(maxLen[i][j-1] , 
                        maxLen[i-1][j]);
                /*打印 可以看出过程 for (int i = 1; i <= length1; i++) { for (int j = 1; j <= length2; j++) { cout << maxLen[i][j] << " "; } cout << endl; } cout <<endl; */
            }
        }
        cout << maxLen[length1][length2];
    }
} //时间复杂度O（nm）2个子串长度