http://acm.pku.edu.cn/JudgeOnline/problem?id=1159
這個(gè)題有兩種基本解法，第1種方法：
設(shè)a[i][j]表示從第i個(gè)字符到第j個(gè)字符需要增加多少字母使得回文，初始化后,狀態(tài)轉(zhuǎn)移方程：
if(s[i]==s[j])
a[i][j]=a[i+1][j-1];
else
a[i][j]=min(a[i+1][j],a[i][j-1])+1;
注意內(nèi)存限制。用short型剛剛好。
第2種解法：
此題可轉(zhuǎn)換成求最長回文子串
即S與^S的最長公共子序列，則answer=n-LCS(S,^S).