LCSと同様． \(s,t\) の最後の文字 \(s_{i}, t_{j}\) を使うかどうかで場合分け． \(s_{[0,i)}, t_{[0,j)}\) に対する答えを \(dp_{i,j}\) とおく．
- \(s_{i} \neq t_{j}\) のとき：使った方が良い． 言い換えると，使う最適な選び方が存在する． このとき\(dp_{i,j} + 1\) ．
- \(s_{i} = t_{j}\)のとき： どちらかは使えない．
- \(s_{i}\) を使わない場合： \(dp_{i,j+1}\)．
- \(t_{j}\) を使わない場合： \(dp_{i+1,j}\)．
初期化
\(i,j\) のどちらかが \(0\) のとき， \(dp_{i,j} = 0\) になる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
string s,t; cin >> s >> t;
ll n = s.length(), m = t.length();
vvll dp(n+1, vll(m+1, 0));
rep(i,n+1) dp[i][0] = 0;
rep(j,m+1) dp[0][j] = 0;
rep(i,n){
rep(j,m){
ll now = dp[i][j];
ll* ne = &dp[i+1][j+1];
if(s[i] != t[j]){
// i,jを使う
chmax(*ne, now + 1);
}else{
// i,jを使わない
// i.e. i を使わない または jを使わない
chmax(*ne, dp[i][j+1]);
chmax(*ne, dp[i+1][j]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
