莫欺少年穷，修仙之旅在这开始—>算法基础课题解

思路：

1. f[i][j] 表示第一个字符串的前 i 个字符，第二个字符串的前 j 个字符的最长公共子序列
2. 状态计算有四种情况：00，01，10，11
3. 00: f[i-1][j-1]
4. 01: f[i-1][j] 包含这种情况
5. 10: f[i][j-1] 包含这种情况
6. 11: 若 a[i] == b[j]，则 f[i-1][j-1] + 1
7. f[i-1][j] 和 f[i][j-1] 包含 f[i-1][j-1]，故 f[i-1][j-1] 可无需计算
8. 所以 f[i][j] = max(f[i-1][j], f[i][j-1])
9. 若 a[i] == b[j]，f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1] + 1}

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main()
{
    cin>>n>>m>>a+1>>b+1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]); // 00，01，10
            if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; // 11
        }

    cout<<f[n][m]<<endl;

    return 0;
}