https://emtubasa.hateblo.jp/entry/2019/01/31/190622

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

解法

求める文字列の長さだけなら、よくある問題です。
ですが、今回は文字列自体も求めなければいけないので、DPの遷移の際に、たどってきた1つ手前の値を一緒に記録してあげればよいです。
まず、文字列の長さのDPについて考えます。
$dp[i][j] = s$ については $i$ 文字目まで、 $t$ については $j$ 文字目までに制限した場合の、求める文字列の長さの最大値
とします。
$dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+x)$
となります。ここで、 $x$ は、 $s_{i}=t_{j}$ なら1、そうでなければ0です。
この遷移をする際に、遷移元候補3種類のうちどれを選択したか、という情報を、 $dp[i][j]$ に記録しておきます。
すると、最終的にdpの値が最大だった $i,j$ のペアを $(x,y)$ とすると、そこから遷移元をたどっていけば、答えを求めることができます。
具体的には、まず $s_{x} = t_{y}$ だったとき、その文字を使用していることになるので、その文字をstring型の変数に記録しておきます。違った場合はスルーします。そして、 $(x,y)$ の値を、 $dp[x][y]$ に記録してある遷移元の値に変更し、この操作を繰り返していきます。すると、用意しておいたstring型の変数には、答えが逆順に記録されています。ので、あとは逆順で出力すれば、答えとなります。