Description:
N種類の文字から成るM文字の文字列が与えられる。
この文字列に文字を追加/削除して、回文にしたい。
各種の文字の追加/削除にかかるコストが与えられるので、最小のコストを求めて欲しい。
Answer:
回文に不要な文字を削除する操作は、その文字に対応する場所に同じ文字を入れて回文の要素にする操作と対応するので、結局コストの安い方しか使わない。
それなら、普通のPalindromeの問題と同じ。
X文字目からY文字目までを回文に修正するコストをメモ付き探索で求めればよい。
Source: