==>原题链接
题目概述
给定一个字符串，可以在任意位置增、删，增删都有相应的成本，你的目的是通过增删来得到一个回文串。
给出最小的成本。
思路
DP。区间DP。
递推方程
if (str[i] != str[j])
{
dp[i][j] = min(dp[i+1][j] + w[str[i]-'a'], dp[i][j-1] + w[str[j]-'a']);}
else
{
dp[i][j] = dp[i+1][j-1];}
dpi 表示字符串从字母 i 到 字母 j 的字串得到回文串需要的最小成本。
可以分为四种情况，增、删前面的一个字母 和 增删 子串最后面一个字母。由于题目表示可以在任意地方增删，那么，一个字母的时候原本就是回文串，两个字母的时候增删左右皆可，三个字母的时候，我们已经讨论过两个字母的情况，因而只需要加上相邻两个字母的di即相当于认为那两个字母已经通过某些神秘的变换变为回文串，因而可以被三个字母的情况利用，对上一阶段结果的存储和利用，满足最优结果，所以可以DP。
而之所以递推式只有两种情况，是因为 在前面增 == 在后面删 对应的字母，那么四种情况就可以简化为两种对应的情况，而使用i+1和j-1是为了使每次递推结果范围缩小。
编写代码的过程中几次wa，遇到的有两个问题：
1.循环顺序错误。既然di依赖于di+1和di，那么在求di的时候，理应已经求出这两种分岔。既然i+1在i前面求得，那么 i = l - 1 to 1 ，而 j-1 在 j 前求得，j = 1 to l - 1，又区间为i..j，所以，j > i, j应该从i+1开始。
2.初始化错误。首先需要巩固的是全局变量和静态变量在定义的时候即被自动初始化为0。其次开始为除了di的值均赋了INF，但实际上，除了di，诸如di+1这类的值也因被赋值为0，这类被赋值为INF导致结果出错。须注意。而实际上赋INF的初衷是求最小应该先赋一个大值，但是，i == j 时，di = dj，自动就是原始的0，其他值由其衍生，也不会出问题，可见这种“保险”是可以不必的，而为了达到“保险”反而会赋很多初值造成大量时间空间的浪费，不必要。
代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
void init();
void solve();
const int N = 2000 + 10,
INF = 1000000000;
char str[N], p[5];
int w[30];
int dp[N][N];
int main()
{
int i, j;
int n, l, ad, in;
freopen("3280.in", "r", stdin);
scanf("%d%d", &n, &l);
scanf("%s", str);
for (i = 0; i < n; i++)
{
scanf("%s%d%d", p, &ad, &in);
w[p[0] - 'a'] = ad < in ? ad : in;
}
for (i = l - 2; i >= 0; i--)
{
for (j = i + 1; j < l; j++)
{
if (str[i] != str[j])
{
dp[i][j] = min(dp[i+1][j] + w[str[i]-'a'], dp[i][j-1] + w[str[j]-'a']);
}
else
{
dp[i][j] = dp[i+1][j-1];
}
}
}
printf("%d\n", dp[0][l-1]);
return 0;
}