EDPC F ~Longest Common Subsequence~

atcoder.jp

LCS(Longest Common Subsequence)をもとめよう。

典型典型と言ってるわりに以外に詰まった問題。反省しろ。

文字列の中身を1文字目, 2文字目, 3文字目...とすると

dp[i][j]: 一つ目の文字列が i 文字目まで、二つ目の文字列が j 文字目まで見た時の最長の増加列

と定めると

for (int i = 0; i < s.size(); i++) {

    for (int j = 0; j < t.size(); j++) {

        if (s[i] == t[j]) {

            dp[i + 1][j + 1] = dp[i][j] + 1;

        } else {

            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);

                  }

        }

}

のような漸化式を組む。

説明は蟻本のとおり、インデックスに気をつけろ！

経路復元について

dpの経路復元として２通りあり

１．dp更新と共に経路まで更新する

２．dpの最後の答えから、逆算する。

２．を採用するとき、「数通りの状態から遷移して同じ答えになる」という状況に遭うと思うがもちろん、値が同じなのでいずれか一つの経路復元の場合は、どれを採用してもよい

ソースコード

https://atcoder.jp/contests/dp/submissions/4577102

～まとめ～

・　経路復元はdpの配列の遷移の方法の真逆とたどれば経路復元できる。

どれからも同じように来てるといえる場合はどれでもよい（これが複数の復元しうる経路となる）

以上