最长公共子序列

如何求解最长公共子序列
状态方程:f[i][j] = if(s1[i] == s2[j])f[i - 1][j - 1] + 1;
else max(f[i - 1][j], f[i][j - 1]);
建立一个二维数组,二维数组的横坐标就是第一个子串的每一个字母,二维数组的纵坐标就是第二个字串的每一个字母,那么对于第一个子串,对于每一个字母s1[i],都用第二个字串遍历一遍,
如果第二个字串的当前字母s2[j]和第一个子串当前字母s1[i]相同,那么就当前的最长公共子序列肯定可以更长,因为当前两个子串字母相等,所以在前面的基础上加一,前面的子串的最长的公共子序列存储在f[i - 1][j - 1]这里,所以当前f[i][j] = f[i - 1][j - 1] + 1;
如果当前字母s2[j]不等于s1[i]那么就保存上一个最大的公共子序列长度f[i][j] = max(f[i - 1][j], f[i][j - 1]);

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000;
int f[N][N];
int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m ; j ++ )
        {
            if(s1[i] == s2[j])f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

最长公共子序列

原文：https://www.cnblogs.com/jw-zhao/p/14769924.html