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

代码

#include<iostream>
   #include<algorithm>
   #include<string>
   using namespace std;
   const int maxn = 1010;
   class Solution
   {
   public:
       void xuliechangdu(string a,string b, int** Maxnum, int **f,int len1,int len2)
       {//求应删除的个数
	reverse(b.begin(), b.end());
	for (int m = 0; m < len1; m++)
	{
		Maxnum[m][0] = 0;
		Maxnum[0][m] = 0;
	}
	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			if (a[i - 1] == b[j - 1])
			{
				Maxnum[i][j] = Maxnum[i - 1][j - 1] + 1;
				f[i][j] = 1;
			}
			else if (Maxnum[i - 1][j] > Maxnum[i][j - 1])
			{
				Maxnum[i][j] = Maxnum[i - 1][j];
				f[i][j] = 2;
			}
			else
			{
				Maxnum[i][j] = Maxnum[i][j - 1];
				f[i][j] = 3;
			}

		}

	}
	int result =len1- Maxnum[len1][len2];
	cout << result << endl;


}
void printzixulie(string a, int **f,int n,int m,string &re)//打印出回文串
{
	
	if (m ==0|| n== 0)
		return;
	else if (f[n][m] == 1)
	{
		printzixulie(a, f, n - 1, m - 1,re);
		re.push_back(a[n - 1]);
		cout << a[n - 1] << endl;
	}
	else if (f[n][m] == 2)
		printzixulie(a, f, n - 1, m,re);
	else
		printzixulie(a, f, n, m - 1,re);
	
}
void PrintOneLCS(string &str1, string &str2, int i, int j,
	int** &veca) {
	
	string lcs_str;
	while (i > 0 && j > 0) {
		if (str1[i - 1] == str2[j - 1]) {
			lcs_str = str1[i - 1] + lcs_str;
			--i;
			--j;
		}
		else {
			//如果左边存在LCS就从左边找否则再从右边找
			if (veca[i - 1][j] >= veca[i][j - 1])
				--i;
			else
				--j;
		}
	}
	cout << lcs_str << endl;
}
void allprint(string &s,string &b,int i,int j,int**&Maxnum,string re)
{
	
	while (i > 0 && j > 0) {
		if (s[i - 1] == b[j - 1]) {
			re = s[i - 1] + re+" " ; //逆向存放
			cout << re << endl;
			--i;
			--j;
		}
		else {
			if (Maxnum[i - 1][j] > Maxnum[i][j - 1]) //向左走
				--i;
			else if (Maxnum[i - 1][j] < Maxnum[i][j - 1]) //向上走
				--j;
			else { //此时向上向右均为LCS的元素
				allprint(s, b, i - 1, j, Maxnum, re);
				allprint(s, b, i, j - 1, Maxnum, re);
				return;
			}
		}
	}
	cout<< re << endl;
	/*re.insert(lcs_str);*/
}

   int main()
   {
       string s;
       while (cin >> s)
       {
           string b = s;
           string re;
           string str2=s;
           reverse(str2.begin(), str2.end());
           int len1 = s.length();
           int len2 = b.length();
           const int maxn = 1010;
           int **Maxnum;
           Maxnum = new int *[maxn];
           for (int i = 0; i < maxn; i++)
               Maxnum[i] = new int[maxn];
       /*	int Maxnum[maxn][maxn];*/
           Solution so;
           int **f;
           f = new int*[maxn];
           for (int j = 0; j < maxn;j++)
               f[j]=new int[maxn];
           //so.xuliechangdu(s,b,Maxnum,f,len1,len2);
           //so.printzixulie(s,f,len1,len2,re);
           //so.PrintOneLCS(s, str2, len1, len2, Maxnum);
           /*so.allprint(s,str2,len1,len2, Maxnum, re);*/
           so.zichuanchangdu(s, b, Maxnum, f, len1, len2);
           cout << re << endl;
           for (int q = 0; q < maxn; q++) {
               delete[] Maxnum[q];
           }
           delete[]Maxnum;
       }


   }

算法

这道题可以看成是求解一个序列和此序列倒序列的最长公共子序列长度问题（LCS），解决此类方法的算法核心是动态规划算法

动态规划算法

序列A=(a1,a2,a3……an)，序列B=(b1,b2,b3……bm)，它们的LCS为序列C(c1,c2,c3……ck)

1
2
3

如果an=bm,则ck=an=bm，且ck-1是an-1和bm-1的LCS
如果an≠bm，则ck≠an，所以c是an-1和bm的LCS
如果an≠bm，则ck≠bm，所以c是bm-1和an的LCS

所以，用p(i,j)来表示序列长度

1
2
3

当n=0，或m=0，p(n,m)=0
当n，m≠0，且an=bm，p(n,m)=p(n-1,m-1)+1
当n，m≠0，且an≠bm，p(n,m)=max{p(n-1,m),p(n,m-1)}

对应上述的xuliechangdu函数

补充

当找到回文串时，需要把这个回文串打印出来，利用动态规划的逆想法，如上述的

1 2	void printzixulie(string a, int **f,int n,int m,string &re) {}

通过对求取序列长度函数中的tag标号来判断当前下标的字符是否需要输出，同样利用递归的思想，逐个输出tag为1时相对应下标的字符。

注意

本文所述的算法仅适用于本题算法，动态规划问题可以求取两个不同字串的公共字符串长度，需要在本文的算法上稍作修改

1 2	1.对于输入，需要输入两个不同的字符串 2.对于输出，由于公共子串不一定是回文，所以本文的输出是从后往前输出，需要注意反序