最长公共子序列（非连续）

这一类LCS问题是最常见的。

给定两个字符串a,b，求a,b的最长公共子序列的长度

状态转移方程

核心代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int LCS_Len(string a, string b)
{
    int dp[1000][1000];
    for(int i = 1; i <= a.size(); i++)
        for(int j = 1; j <= b.size(); j++){
            if(a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    return dp[a.size()][b.size()];
}

最长公共子序列（连续）

给定两个字符串a,b，求a,b的最长公共连续子序列的长度

这里要保证最长公共子序列一定要是连续的。

状态转移方程

在这里插入图片描述

最后在dp数组中寻找一次最大值，这个值就是最大长度

核心代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int Similar(string a, string b)
{
    int dp[100][100];
    for(int i = 1; i <= a.size(); i++){
        for(int j = 1; j <= b.size(); j++){
            if(a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else{
                dp[i][j] = 0;
            }
        }
    }
    int max = -1;
    for(int i = 1; i <= a.size(); i++)
        for(int j = 1; j <= b.size(); j++)
            if(max <= dp[i][j])
                max = dp[i][j];
    return max;
}