看到Palindrome的题目，首先想到的应该是中心问题，然后从中心出发，思考如何解决。

DP问题一般是从更加小的问题转化到更加大的问题，然后是从地往上 bottom up地计算答案的。

能得出状态转移方程就好办了，本题的状态转移方程是：

if (cowID[i] == cow{j]) tbl[id][i] = tbl[id][i+1];//相等的时候无需改动

else tbl[id][i] = min(tbl[!id][i+1] + cost[cowID[i]-'a'], tbl[!id][i] + cost[cowID[j]-'a']);//不相等的时候需要看改动那一边的字符比较划算

注意：

1 cost的删除和插入对于DP来说实际是一样的操作，所以只需要报出一个最小的cost就可以了

2 cost的值是以字母为下标保存值的，不是按顺序给出的，也可能某些字母的值没有给出，这个时候默认应该为零

最后是需要节省内存，这些题目一般可以只看一维dp table数组就可以了，这个时候要二维转化为一维保存结果，实际测试内存节省非常多。

这里使用所谓的滚动数组，轮流使用两个数组记录数据。

主要把二维表的斜对角格转为一个数组保存，对应好下标就可以了。

#include 
  
   
#include 
   
     const int MAX_M = 2001; const int MAX_N = 26; char cowID[MAX_M]; int cost[MAX_N];//minimum of the cost of adding and deleting that character. int tbl[2][MAX_M]; int N, M; inline int min(int a, int b) { return a < b ? a : b; } int getMinCost() { memset(tbl[0], 0, sizeof(int)*M); memset(tbl[1], 0, sizeof(int)*M); bool id = false; for (int d = 2; d <= M; d++) { id = !id; for (int i = 0, j = d-1; j < M; i++, j++) { if (cowID[i] == cowID[j]) tbl[id][i] = tbl[id][i+1]; else { int c1 = tbl[!id][i+1] + cost[cowID[i]-'a']; int c2 = tbl[!id][i] + cost[cowID[j]-'a']; tbl[id][i] = min(c1, c2); } } } return tbl[id][0]; } int main() { char a; int c1, c2; while (scanf("%d %d", &N, &M) != EOF) { memset(cost, 0, sizeof(int)*N); getchar(); gets(cowID); for (int i = 0; i < N; i++) { a = getchar(); scanf("%d %d", &c1, &c2); cost[a-'a'] = min(c1, c2);//only need to save the minimum getchar(); } printf("%d\n", getMinCost()); } return 0; }