一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1e3+10;

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

class DP
{
public:
    int f[N][N];

public:
    DP()
    {
        initIO();
        fill(f[0], f[0]+N*N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    int work()
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                f[i][j]=max(f[i][j-1], f[i-1][j]);
                if(a[i]==b[j]) f[i][j]=max(f[i][j], f[i-1][j-1]+1);
            }

        return f[n][m];
    }
}dp;

int main()
{
    cin>>n>>m>>a+1>>b+1;
    cout<<dp.work();
}