给一个串，问最少添加几个字符使得 该串 变成回文串，dp。。
dp[i][j]表示 i j 的范围内需要添加几个字符，如果 s[i]==s[j],那么 dp[i][j]=dp[i+1][j-1];
否则 ，dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
ps: 用short水过，int MLE 啊 啊啊啊。。
[cpp]
#include
#include
#include
using namespace std;
const int maxn=5002;
char s[maxn];
short dp[maxn][maxn];
int main(){
short n;
while(scanf("%d",&n)!=EOF){
scanf("%s",s);
memset(dp,0,sizeof(dp));
for(short i=n-1;i>=0;i--)//i指针表示从左端开始
for(short j=0;j
if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];
else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
}
printf("%d\n",dp[0][n-1]);
}
}
记忆化搜索，卡时过的，效率好低啊。。
[cpp]
#include
#define min(a,b) ((a)<(b) (a):(b))
const int maxn=5002;
char s[maxn];
short dp[maxn][maxn];
short n;
short dfs(short i,short j){
if(dp[i][j]!=-1)return dp[i][j];
if(i==n-1||j==0||i==j)return dp[i][j]=0;
if(s[i]==s[j])return dp[i][j]=dfs(i+1,j-1);
short a=dfs(i+1,j);
short b=dfs(i,j-1);
return dp[i][j]=min(a,b)+1;
}
int main(){
while(scanf("%d",&n)!=EOF){
scanf("%s",s);
//memset(dp,-1,sizeof(dp));
for(short i=0;i<=n;i++)for(short j=0;j<=n;j++)dp[i][j]=-1;
dfs(0,n-1);
printf("%d\n",dp[0][n-1]);
}
}
作者：qingniaofy