d.求对字符串最少添加几个字符可变为回文串。
s.
法1：直接对它和它的逆序串求最长公共子序列长度len。N-len即为所求。(N为串长度)
因为，要求最少添加几个字符，我们可以先从原串中找到一个最长回文子序列，然后对于原串中不属于这个回文子序列的字符，在串中的相应位置添加一个相同的字符即可。那么需要添加的字符数量即为N-len。
最长回文串可以看作是原串中前面和后面字符的一种匹配（每个后面的字符在前面找到一个符合位置要求的与它相同的字符）。这种的回文匹配和原串与逆序串的公共子序列是一一对应的（一个回文匹配对应一个公共子序列，反之亦然），而且两者所涉及到的原串中的字符数量是相等的，也就是最长公共子序列对应最长回文串。原因陈述完毕。
dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列
if(str[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
法2：
dp[i][j]表示从i到j这段子串若变为回文串最少添加的字符数。
if(str[i]==str[j]){
dp[i][j]=dp[i+1][j-1];
}
else{
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
}
c.法1
/*
用short险过 dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列 if(str[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
} */
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 5005 short dp[MAXN][MAXN];
char str[MAXN],str2[MAXN]; int main(){ int N;
int i,j; while(~scanf("%d",&N)){ scanf("%s",str); for(i=,j=N-;i<N;++i,--j){
str2[i]=str[j];
} memset(dp,,sizeof(dp));
for(i=;i<=N;++i){
for(j=;j<=N;++j){
if(str[i-]==str2[j-]){
dp[i][j]=dp[i-][j-]+;
}
else{
dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
} printf("%d\n",N-dp[N][N]);
} return ;
}
ps：其实可以用滚动数组
c'.滚动数组
/*
用short险过 dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列 if(str[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
} */
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 5005 short dp[][MAXN];//滚动数组
char str[MAXN],str2[MAXN]; int main(){ int N;
int i,j; while(~scanf("%d",&N)){ scanf("%s",str); for(i=,j=N-;i<N;++i,--j){
str2[i]=str[j];
} memset(dp,,sizeof(dp));
for(i=;i<=N;++i){
for(j=;j<=N;++j){
if(str[i-]==str2[j-]){
dp[i%][j]=dp[(i-)%][j-]+;
}
else{
dp[i%][j]=max(dp[(i-)%][j],dp[i%][j-]);
}
}
} printf("%d\n",N-dp[N%][N]);
} return ;
}
c2.法2
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 5005 short dp[MAXN][MAXN];
char str[MAXN]; int main(){ int N;
int i,j; while(~scanf("%d",&N)){
scanf("%s",str); memset(dp,,sizeof(dp)); for(i=N-;i>=;--i){
dp[i][i]=;
for(j=i+;j<N;++j){
if(str[i]==str[j]){
dp[i][j]=dp[i+][j-];
}
else{
dp[i][j]=min(dp[i+][j],dp[i][j-])+;
}
}
} printf("%d\n",dp[][N-]);
} return ;
}
c2'.滚动数组
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 5005 short dp[][MAXN];//滚动数组
char str[MAXN]; int main(){ int N;
int i,j; while(~scanf("%d",&N)){
scanf("%s",str); memset(dp,,sizeof(dp)); for(i=N-;i>=;--i){
dp[i%][i%]=;
for(j=i+;j<N;++j){
if(str[i]==str[j]){
dp[i%][j]=dp[(i+)%][j-];
}
else{
dp[i%][j]=min(dp[(i+)%][j],dp[i%][j-])+;
}
}
} printf("%d\n",dp[][N-]);
} return ;
}