自己想的思路，做了两个多小时，又改了一会，dp还是要认真想啊。。。希望慢慢有进步。
题意：给一个m个字符的字符串，全是小写字母，一共有n个不重复的字母，分别给出n个字母的插入和删除费用，删除或插入任意字符 使 字符串成为回文串，求最小的费用。
分析：d[i][j]表示从 i 到 j 变成回文的最小费用，计算时先计算j-i 最小的，也就是从相邻 的开始计算，慢慢累加。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #define LL long long 7 using namespace std; 8 const int maxn = 2000 + 10; 9 char s[maxn]; 10 int n, m, ad[300], de[300]; 11 int d[maxn][maxn]; 12 13 int main() 14 { 15 int i, j; 16 char ch; 17 while(~scanf("%d%d", &n, &m)) 18 { 19 memset(d, 0, sizeof(d)); 20 memset(ad, 0, sizeof(ad)); 21 memset(de, 0, sizeof(de)); 22 getchar(); 23 scanf("%s", s); 24 for(i = 0; i < n; i++) 25 { 26 getchar(); 27 scanf("%c", &ch); 28 scanf("%d%d", &ad[ch], &de[ch]); 29 } 30 for(i = 1; i < m; i++) //间隔个数 31 { 32 for(j = 0; j+i < m; j++) //开始的位置 33 { 34 if(s[j] == s[j+i]) 35 d[j][j+i] = d[j+1][j+i-1]; 36 else 37 { 38 d[j][j+i] = min(d[j][j+i-1]+ad[s[j+i]], d[j][j+i-1]+de[s[j+i]]); 39 int x = min(d[j+1][j+i]+ad[s[j]], d[j+1][j+i]+de[s[j]]); 40 if(x < d[j][j+i]) 41 d[j][j+i] = x; 42 } 43 } 44 } 45 printf("%d ", d[0][m-1]); 46 } 47 return 0; 48 }