构造回文

时间限制：1秒

空间限制：32768K

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子1:
abcda
google

输出例子1:
2
2

题解

原串 - 最大公共子序列 = 最小编辑距离

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int dp[maxn][maxn];
int LCS(string s1, string s2){
	s1 = "#"+ s1; //为了从1号位开始比较 
	s2 = "#"+ s2; //#没有任何含义，只是占位
	
	for(int i=0;i<s1.size();i++) dp[i][0]=0;
	for(int i=0;i<s2.size();i++) dp[0][i]=0;
	for(int i=1;i<s1.size();i++){
		for(int j=1;j<s2.size();j++){
			if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
		}
	}
	return dp[s1.size()-1][s2.size()-1];
}
int main(){
	string s1,s2;
	while(cin>>s1){
		if(s1.size() ==1){
			cout<<"1"<<endl;
			continue;
		}
		memset(dp,0,sizeof(dp));
		s2 = s1;
		reverse(s2.begin(), s2.end());
		int len = LCS(s1,s2);
		cout<<s1.size()-len<<endl;
	}
	return 0;
}