Educational DP Contest / DP まとめコンテスト F - LCS

問題
提出コード
明らかにMLEを起こしそうなコードを提出するのはやめましょう。

解法

求める文字列の長さだけなら、よくある問題です。
ですが、今回は文字列自体も求めなければいけないので、DPの遷移の際に、たどってきた1つ手前の値を一緒に記録してあげればよいです。
まず、文字列の長さのDPについて考えます。
については文字目まで、については文字目までに制限した場合の、求める文字列の長さの最大値
とします。

となります。ここで、は、なら1、そうでなければ0です。
この遷移をする際に、遷移元候補3種類のうちどれを選択したか、という情報を、に記録しておきます。
すると、最終的にdpの値が最大だったのペアをとすると、そこから遷移元をたどっていけば、答えを求めることができます。
具体的には、まずだったとき、その文字を使用していることになるので、その文字をstring型の変数に記録しておきます。 違った場合はスルーします。そして、の値を、に記録してある遷移元の値に変更し、この操作を繰り返していきます。すると、用意しておいたstring型の変数には、答えが逆順に記録されています。ので、あとは逆順で出力すれば、答えとなります。