题目大意是说一个字符串，每插入或者删除一个字符都需要一定的代价，问怎样可以使这个字符串变成一个回文串，且花费最小。
题解：我们定义一个dp[i][j]表明区间i~j为回文串的最小花费，由于插入和删除都是可以任意位置进行的，所以无后效性。然后状态转移和以前的回文串的状态转移差不多。
（新的理解，搞回文串的问题之所以可以从 d[i+1][j] d[i][j-1] 以及dp[i+1][j-1]三个点入手，是因为这三者的并集能够覆盖所有的情况）
ac代码：
#include <cstdio> #include <iostream> #include <cstring> #include <string> #define mt(a) memset(a,0,sizeof(a)) using namespace std; int cost[2022]; int dp[2002][2002]; int s[2011]; const int inf=0x3f3f3f; int main() { int n,m; scanf("%d %d",&n,&m); string ss; cin>>ss; int len=ss.size(); for(int i=0;i<len;i++) { s[i+1]=ss[i]-'a'; //dp[i+1][i+1]=0; } while(n--) { string z; cin>>z; int key=z[0]-'a'; int x,y; cin>>x>>y; cost[key]=min(x,y); } for(int l=2;l<=len;l++) { for(int i=1;i+l-1<=len;i++) { int j=i+l-1; dp[i][j]=min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]); if(s[i]==s[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); } } cout<<dp[1][len]<<endl; return 0; }