最短回文串(序列型DP) 解题日志

最短回文串(palindrome)

【问题描述】

如果一个字符串正过来读和倒过来读是一样的,那么这个字符串就被称作回文串。例如abcdcba,abcddbca就是回文串,而abcdabcd不是。

你要解决的问题是:对于任意一个字符串,输出将这个字符串变为回文串需要插入的最少字符个数,比如,ab3bd只需要插入2个字符就可以变为一个回文串。

【输入格式】

第一行是一个整数N

第二行是一个长度为N字符串S

【输出格式】

一行一个整数,表示将S变为回文串需要插入的最小字符个数

【输入样例 】

5

ab3bd

【输出样例】

2

【数据范围 】

对于所有数据,0<n<=5000

 

 

思路一:

设f(i,j)为将Ai..Aj变为回文串的最小代价,则

 

一共有n^2个状态,状态转移是O(1)的,总的复杂度为O(n^2)

 

for(int i=n; i>0; i--)

   for(int j=i+1; j<=n; j++)

   if (a[i]==a[j]) f[i][j]= f[i+1][j-1];

   else

       f[i][j]=min(f[i+1][j], f[i][j-1])+1;

 

cout<< f[1][n]<< endl;

  

 

思路二:

将原串与原串的倒序做一次LCS—最长公共子序列,用原串长度减去LCS长度,即为需要插入字符的个数

例如:ab3bd与 db3ba

LCS(‘ab3bd’, ‘db3ba’)=‘b3b’

因此, ans=Len(‘ab3bd’)-Len(‘b3b’)=2

#include<bits/stdc++.h>
using namespace std;
void FUCK(string name){
	string i=name+".in";
	string o=name+".out";
	freopen(i.c_str(),"r",stdin);
	freopen(o.c_str(),"w",stdout);
}
string a,b,s;
int dp[5001][5001],n;
int main(){
	FUCK("palindrome");
	//program here
	cin>>n>>s;
	a=b=s;
	for(int i=0;i<a.size();i++){
		b[a.size()-i-1]=a[i];
	}
	dp[0][0]=0;
	for(int i=1;i<a.size();i++){
		for(int j=1;j<b.size();j++){
			dp[i][j]=0;
			if(a[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}
			if(dp[i-1][j]>dp[i][j]){
				dp[i][j]=dp[i-1][j];
			}
			if(dp[i][j-1]>dp[i][j]){
				dp[i][j]=dp[i][j-1];
			}
		}
	}
	int hehehe = dp[a.size()-1][b.size()-1];
	cout<<a.size()-hehehe<<endl;
	return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注