「みんなのプロコン」2017 本選 A - YahooYahooYahoo
解法
典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる.
(は正規表現における閉包)
i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう.
それまでの最小の編集距離に注目する上では, 末尾が "yahoo" の何番目になっているかということにだけ注目すれば良い.
よって, dp[i][j] := (S[0,i) を 末尾が"yahoo"のj番目(0-index)になるようにした,最小の編集距離 ) とする.
すると, 遷移は dp[i][j] からs[i] をそのまま足して 1<=k<=5 回末尾に insert, または末尾を 1回deleate したパターンを考えればわかる.
1<=k<=5 回でなく1回だけinsertすると考えて dp[i][j] から dp[i][j+1] に遷移させることもできるが, その場合解説にあるように2周しないといけない.
初期値と答えに注意.
