<题目链接>
题目大意：
一个由小写字母组成的字符串，给出字符的种类，以及字符串的长度，再给出添加每个字符和删除每个字符的代价，问你要使这个字符串变成回文串的最小代价。
解题分析：
一道区间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+5; int n,m,dp[N][N],add[26],del[26]; char str[N]; int main(){ scanf("%d%d",&n,&m); scanf("%s",str+1); for(int i=1;i<=n;i++){ char c;cin>>c; int pos=c-‘a‘; scanf("%d%d",&add[pos],&del[pos]); } for(int i=m;i>=1;i--){ dp[i][i]=0; for(int j=i+1;j<=m;j++){ dp[i][j]=1e9; if(str[i]==str[j])dp[i][j]=dp[i+1][j-1]; dp[i][j]=min(dp[i][j],dp[i+1][j]+min(add[str[i]-‘a‘],del[str[i]-‘a‘])); dp[i][j]=min(dp[i][j],dp[i][j-1]+min(add[str[j]-‘a‘],del[str[j]-‘a‘])); } } cout<<dp[1][m]<<endl; }
POJ 3280 Cheapest Palindrome (区间DP) 经典
原文：https://www.cnblogs.com/00isok/p/10639232.html