题意：
给定一个长度为m的字符串（都是小写字母） ，求通过添加或者删减若干个字符是原字符串变为回文串的最小代价（这里给出n个字符的删除与添加所需的代价，规定添加和删除的字符串都在给定的这n个字符中）；
思路：
只能说自己dp太弱了，以后有时间一定要多练习dp。
这里对字符串从两端开始进行比较如果相同则dp[i][j] = dp[i + 1][j - 1],
如果不同则 dp[i][j] = min(dp[i + 1][j] + min(addv[str[i] -'a'],delv[str[i] - 'a']),dp[i][j - 1] + min(addv[str[j] -'a'],delv[str[j] - 'a']));
这个题解比较好粘贴过来用一下：
其实dp很难逃出3种思路：
1、一维线性dp：每次考虑i时，选择最优子问题要么在i-1，要么在1...i-1里；
2、二维线性dp：考虑(i,j)子问题时，选择最优子问题要么在(i+1,j)、(i,j-1)，要么在i<= k <=j，在k里；
3、树形dp：考虑i节点最优时，选择子节点最优，一般融合了01背包dp的双重dp。
上面3中模式也是我在做题后才发现的。
这个dp题其实就可以仿照第2中思路。
假设一个字符串Xx....yY；对于求这个字符串怎么求呢？
分4中情况讨论：
1、去掉X，取x....yY回文；
2、去掉Y，取Xx....y回文；
3、在左边加上X,取Xx....yYX回文；
4、在右边加上Y,取YXx....y回文。
至于去掉X、Y肯定没有第1、2中情况合算；加上X、Y肯定没有第3、4中情况合算。
因此令dp[i][j]为i...j要变成回文字符串的最小代价。
方程：
dp[i][j] = min{ dp[i+1][j] + {去掉X的代价}，dp[i+1][j] + {加上X的代价}，
dp[i][j-1]+ {去掉Y的代价}，dp[i][j-1] +{加上Y的代价}}；
其实分析发现，对于X而言，只要去 去掉 和加上 X 最小代价就行（因为前面dp串一样）,Y同理。
因此最后得出：
dp[i][j] = min{ dp[i+1][j] +min{ {去掉X的代价}, {加上X的代价}}，
dp[i][j-1]+min{ {去掉Y的代价}, {加上Y的代价}}}；
感觉如果dp状态转移方程推出来了之后用记忆化搜索比较好些，于是就写了记忆化搜索：
View Code #include#include #include #include #include #define maxn 2007#define N 8using namespace std;const int inf = 99999999;int dp[maxn][maxn];char str[maxn];int addv[27],delv[27];int DP(int i,int j){ if (dp[i][j] != 0) return dp[i][j]; if (i >= j) { dp[i][j] = 0; return 0; } if (str[i] == str[j]) dp[i][j] = DP(i + 1,j - 1); else dp[i][j] = min(DP(i + 1,j) + min(addv[str[i] - 'a'],delv[str[i] - 'a']),DP(i,j - 1) + min(addv[str[j] - 'a'],delv[str[j] - 'a'])); return dp[i][j];}int main(){ //freopen("d.txt","r",stdin); int n,m,i; char ch[3]; int a,b; scanf("%d%d",&n,&m); scanf("%s",str); for (i = 0; i < n; ++i) { scanf("%s%d%d",ch,&a,&b); addv[ch[0] - 'a'] = a; delv[ch[0] - 'a'] = b; } memset(dp,0,sizeof(dp)); printf("%d\n",DP(0,m)); return 0;}
在附带一个dp的：
View Code #include#include #include #include #define CL(a,num) memset(a,num,sizeof(a))#define maxn 2007#define N 8using namespace std;const int inf = 99999999;int dp[maxn][maxn];char str[maxn];int addv[27],delv[27];int main(){ //freopen("din.txt","r",stdin); int n,m,i,l,j; char ch[3]; int a,b; scanf("%d%d",&n,&m); scanf("%s",str); for (i = 0; i < n; ++i) { scanf("%s%d%d",ch,&a,&b); addv[ch[0] - 'a'] = a; delv[ch[0] - 'a'] = b; } CL(dp,0); for (l = 0; l < m; ++l) { for (i = 0; i + l < m; ++i) { j = i + l; if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = min(dp[i + 1][j] + min(addv[str[i] -'a'],delv[str[i] - 'a']), dp[i][j - 1] + min(addv[str[j] -'a'],delv[str[j] - 'a'])); } } printf("%d\n",dp[0][m - 1]); return 0;}