https://kyopro.hateblo.jp/entry/2019/06/21/033154

問題. 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;
}

最長増加部分列のように動的計画法だろうなとなんとなくで漸化式を作ったら，なんとなくで通ったからダメすぎる（漸化式の意味付けは後出しジャンケン）．
漸化式を考えるときの思考が上手くできていないのでどうにかしないと・・・．

ABC130 E問題：Common Subsequence

問題. Common Subsequence

解法．動的計画法