dp思路：dp[i][j]代表第一个字符串前i个字符和第二个字符串前j个字符的最长公共子序列的长度
其中对于某一个状态dp[j][j]存在四种情况：
1、s[i],t[j]都包括在最长公共子序列中，则有转移：
2、s[i],t[j]都不包含在最长公共子序列中，则有转移：
3、s[i],t[j]只有一个包含在最长公共子序列中，然而这种情况不能由dp[i-1][j]和dp[i][j-1]直接得到，因为dp[i-1][j]代表第一个字符串前i-1个字符以及第二个字符串前j个字符的最长公共子序列长度，但是其中最长公共子序列不一定包含t[j]，而我们需要的情况是一定要包含t[j]的，dp[i][j-1]同理，而且我们也无法找到一个可以直接进行转移的状态，但是我们需要的是dp[i][j]的最大值，而dp[i][j-1]和dp[i-1][j]是各自包括一种情况的，但同时其状态又被包含在dp[i][j]中，所以我们可以直接对dp[i][j-1]和dp[i-1][j]取max然后再对dp[i-1][j-1]取max，最后判断是否存在第一种情况，如果有再取max即可得到 dp[i][j]的最大值,
不难发现，dp[i-1][j]和dp[i][j-1]的所有情况是包括了dp[i-1][j-1]的，所以不需要再对第二种情况取max
ac代码：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
// #define int unsigned long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
string s,t;
int n,m;
int dp[N][N];
void solve()
{cin>>n>>m;cin>>s>>t;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(s[i-1]==t[j-1])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);}}cout<<dp[n][m]<<endl;
}
signed main()
{Mirai;int T=1;//cin>>T;while(T--){solve();}
}
