PKU3280-Cheapest Palindrome

題目：http://poj.org/problem?id=3280
給一長度為M(2000)的小寫字母字串
以及所有出現字母的"增加成本"和"刪除成本"
求讓字串變成回文的最小成本


程式碼：http://codepad.org/C4osiLDj
首先可以很快的看出來
"在相應位置增加字元"和"刪除該字元"意思是一樣的，取較小者即可

立馬決定DP[i,j]表示讓區間[i,j]是回文的最小花費

轉移部分有兩種情形
1.首尾相同：DP[i,j] = DP[i+1,j-1]
2.首尾相異：從"去頭"和"去尾"兩者的成本選一個小的

得解之