原案：kuronosu1024

元の問題

文字列 $S,T$ が与えられます。
文字列 $S$ に以下の3つの操作を好きな回数行うことができます。

• 文字を任意の場所に追加する
• 任意の文字を削除する
• 任意の文字を変更する $S$ を $T$ と一致させるために必要な操作回数の最小値を出力してください。

想定エスパー法

入力が二つの文字列であるのに対し、出力すべき値が整数であることから答えは何かしらの操作回数であるとエスパーします。
有名なものは文字列の編集距離なのでそれを疑います。

サンプル１から文字の追加、削除が可能であることをエスパーします。
サンプル２から文字の変更も可能であることをエスパーします。

サンプル３で上記が正しいことを確認します。

解法

$|S| \times |T|$ が $10^6$ 以下なので動的計画法やメモ化再起などで解くことができます。