最短回文串（序列型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;
}