<题目链接>
题目大意：
一个由小写字母组成的字符串，给出字符的种类，以及字符串的长度，再给出添加每个字符和删除每个字符的代价，问你要使这个字符串变成回文串的最小代价。
解题分析：
一道区间DP的好题。因为本题字符串的长度最大为2e3，所以考虑$O(n^2)$直接枚举区间的两个端点，然后对枚举的区间进行状态转移，大体上有三种转移情况：
$dp[l][r]$表示$[l,r]$为回文串的最小代价
对于区间$[l,r]$，当$str[l]==str[r]$时，$dp[l][r]=dp[l+1][r-1]$
对于$dp[l+1][r]$情况，即$[l+1,r]$为回文串，$dp[l][r]=dp[l+1][r]+min($在$r+1$添加$str[l]$,在$l$删除$str[l])$的代价
对于$dp[l][r-1]$的情况，即$[l,r-1]$为回文串，$dp[l][r]=dp[l][r-1]+min($在$l-1$添加$str[r]$,在$r$删除$str[r])$的代价
记忆化搜索
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std; const int N = 2e3+;
int n,m,dp[N][N],add[],del[];
char str[N]; int DP(int l,int r){
if(l>=r)return ;
if(dp[l][r]!=-)return dp[l][r];
dp[l][r]=1e9;
if(str[l]==str[r])dp[l][r]=DP(l+,r-);
dp[l][r]=min(dp[l][r],DP(l+,r)+min(add[str[l]-'a'],del[str[l]-'a']));
dp[l][r]=min(dp[l][r],DP(l,r-)+min(add[str[r]-'a'],del[str[r]-'a']));
return dp[l][r];
} int main(){
scanf("%d%d",&n,&m);
scanf("%s",str+);
for(int i=;i<=n;i++){
char c;cin>>c;
int pos=c-'a';
scanf("%d%d",&add[pos],&del[pos]);
}
memset(dp,-,sizeof(dp));
printf("%d\n",DP(,m));
}
递推DP
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std; const int N = 2e3+;
int n,m,dp[N][N],add[],del[];
char str[N]; int main(){
scanf("%d%d",&n,&m);
scanf("%s",str+);
for(int i=;i<=n;i++){
char c;cin>>c;
int pos=c-'a';
scanf("%d%d",&add[pos],&del[pos]);
}
//memset(dp,0x3f,sizeof(dp)); //因为下面的[i+1,j-1]可能会出现j<i的情况，所以不能这样初始化为无穷
for(int i=m;i>=;i--){
dp[i][i]=;
for(int j=i+;j<=m;j++){
dp[i][j]=1e9;
if(str[i]==str[j])dp[i][j]=dp[i+][j-];
dp[i][j]=min(dp[i][j],dp[i+][j]+min(add[str[i]-'a'],del[str[i]-'a']));
dp[i][j]=min(dp[i][j],dp[i][j-]+min(add[str[j]-'a'],del[str[j]-'a']));
}
}
cout<<dp[][m]<<endl;
}