题目描述

最长公共子序列

状态表示

f[i][j]表示str1前i子串和str2前j子串的最长公共子序列的长度

递推关系（即寻找当前与先前的关系）

当第str1的i位和str2的第j位相同时，f[i][j]=f[i-1][j-1]+1（当前在先前的基础上+1）
否则，f[i][j]=max(f[i][j-1],f[i-1][j]),例如bqwsd和wsda，两串的最后一位d和a不相等，则考虑bqwsd和wsd 和 bqws和wsda 哪一个公共子序列的更长（当前等于两个先前的最大）

样例

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;//如果待比较字符一样，则长度在先前基础上+1
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);//否则看看先前的哪一种情况更长
        }

    printf("%d\n", f[n][m]);

    return 0;
}