ABC130 E問題：Common Subsequence - 忘れても大丈夫

問題. Common Subsequence

長さ $N$ の整数列 $S$ と長さ $M$ の整数列 $T$ が与えられる． $S$ と $T$ の等しい部分列が何通りあるか求めよ．

制約： $1 \le N, M \le 2 \times 10^3$ ，　 $S$ と $T$ の各要素は 1 以上 $10^5$ 以下

動的計画法で求める．dp[i][j] を連続部分列 $S_1, S_2, \ldots, S_i$ と $T_1, T_2, \ldots, T_j$ の等しい部分列の数と定義する．このとき漸化式は，
　・ $S_i \neq T_j$ の場合： dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
　・ $S_i = T_j$ の場合： dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
となる．ただし，dp[i][0] と dp[0][j] の値は 1 に初期化をする（空の部分列）．

上の漸化式は， $S_i = T_j$ の場合は連続部分列 $S_1, S_2, \ldots, S_{i - 1}$ と $T_1, T_2, \ldots, T_{j - 1}$ の等しい部分列の末尾に $S_i$ と $T_j$ をそれぞれ加えることによって新たな等しい部分列を構成することができることを表している．これは， $S_i \neq T_j$ の場合に新たに構成される部分列の数 dp[i - 1][j - 1] を加えている．

計算時間： $O(N M)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    constexpr ll MOD = 1e9 + 7;

    ll n, m;
    cin >> n >> m;

    vector<ll> s(n), t(m);
    for (ll &s_i : s) cin >> s_i;
    for (ll &t_i : t) cin >> t_i;

    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int j = 0; j <= m; ++j) dp[0][j] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            (dp[i][j] += dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + MOD) %= MOD;
            if (s[i - 1] == t[j - 1]) (dp[i][j] += dp[i - 1][j - 1]) %= MOD;
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}