Common Subsequence [AtCoder Beginner Contest 130 E]

https://atcoder.jp/contests/abc130/tasks/abc130_e

動的計画法

• 動的計画法

解説

https://atcoder.jp/contests/abc130/submissions/6001273

mod10^9+7で制約が10^3くらいなので、dp[10^3][10^3]かなーと経験則的に思う。
2つの数列があって、dp[s][t]であるかなという感じに仮定を立てていく。
dp[s][t] := 数列Sをs番目まで、数列Tをt番目まで使っているときに整数列として等しいような組み合わせ
S[s] == T[t]であれば、それを採用して、dp[s][t] += dp[s - 1][t - 1]という遷移になりそう。
問題が、採用しないときである。
これは、2次元累積和っぽく計算する。
dp[s][t] += dp[s - 1][t] + dp[s][t - 1] - dp[s - 1][t - 1]
これを一気にやってしまえば、dp[N][M]が答えになる。

int N, M, S[2010], T[2010];
mint dp[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, N) cin >> S[i];
	rep(i, 0, M) cin >> T[i];

	dp[0][0] = 1;
	rep(s, 0, N + 1) rep(t, 0, M + 1) {
		if (0 < s and 0 < t and S[s-1] == T[t-1]) dp[s][t] += dp[s - 1][t - 1];

		if (0 < s) dp[s][t] += dp[s - 1][t];
		if (0 < t) dp[s][t] += dp[s][t - 1];
		if (0 < s and 0 < t) dp[s][t] -= dp[s - 1][t - 1];
	}

	cout << dp[N][M] << endl;
}