LCS（最长公共子序列）

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<cstdio>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e3;
string s1, s2;
int dp[maxn][maxn];
int main() {
  int t1, t2;cin >> t1 >> t2;
  cin >> s1 >> s2;
  for (int i = 0;i < t1;++i) {
    for (int j = 0;j < t2;++j) {
      if (s1[i] == s2[j])dp[i + 1][j + 1] = dp[i][j] + 1;
      else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
    }
  }
  printf("%d", dp[t1][t2]);
  return 0;
}