繰り返す呪文 [パソコン甲子園2016 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0341?year=2016

前提知識

• 動的計画法

考察過程

1. 典型問題として覚えてしまっているので、考察過程がなかった
2. 文字列の添字を持つDPを作る
3. 10^9+7での数え上げ、制約もどちらのindexを取れるということでDPで考え出すと解ける

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0341/review/3140111/hamayanhamayan/C++14

DPを作る。
dp[t][b] := 文字列Tのt番目までの文字列から選択して、文字列Bのb番目までを構築する組み合わせ
遷移としては2種類ある。
　
文字列Bのb+1番目を確定できる。
T[t] = B[b]であれば、b+1番目までの構築ができるので、dp[t+1][b+1] += dp[t][b]
　
文字列Bのb+1番目として確定させないことにする。
dp[t+1][b] += dp[t][b]
　
DPがわかっていれば、すぐ思いつくかもしれないが、なれていないと難しい問題。
典型力。

string T, B;
int NT, NB;
mint dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> B;
    NT = T.length(), NB = B.length();

    dp[0][0] = 1;
    rep(t, 0, NT) rep(b, 0, NB) {
         if (T[t] == B[b]) dp[t + 1][b + 1] += dp[t][b];
         dp[t + 1][b] += dp[t][b];
    }

    mint ans = 0;
    rep(t, 0, NT + 1) ans += dp[t][NB];
    cout << ans << endl;
}