わたのはら [いろはちゃんコンテスト Day2 A]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/iroha2019-day2/submissions/5214346

問題を読み替えよう。
どの長さqの部分列も、他の歌の部分列でない。
つまり、最長の共通部分列の長さ+1が答えということになる。
共通部分列はDPで計算できることがよく知られているので、DPする。
　
dp[s][t] := S[0..s]とT[0...t]での共通部分列の最長の長さ
遷移は、特に何もしない遷移のdp[s+1][t], dp[s][t+1]と、
共通部分列の末尾として採用する、S[s]=T[t]のときにdp[s+1][t+1] = dp[s][t]+1とする遷移。
dp[S][T]+1が答え。

string S, T;
int N;
int dp[5010][5010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S >> T;
	N = S.length();
 
	rep(s, 0, N + 1) rep(t, 0, N + 1) {
		chmax(dp[s + 1][t], dp[s][t]);
		chmax(dp[s][t + 1], dp[s][t]);
 
		if (s < N and t < N) if (S[s] == T[t]) chmax(dp[s + 1][t + 1], dp[s][t] + 1);
	}
 
	cout << dp[N][N] + 1 << endl;
}