POJ - 1159 Palindrome(dp-回文变形)

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 ;
}
上一篇:css-css权威指南学习笔记3


下一篇:配置node与express初试