本题的题意理解之后，就是求最长回文子序列 longest palindrome subsequence，这里注意子序列和子串的区别。

有两种求法，一种是直接求，相当于填矩阵右上对角阵，另一种是转化为longest common subsequence的求法。

最大难点就是要求内存不能使用二维的。 故此第一种方法是有点难度的，因为需要把二维矩阵的对角线转化为一维表记录，对好下标就好了。

第二中方法会稍微容易点，效率都是一样的O(n*n)。

方法1：

#include 
  
   

const int MAX_N = 5001;//超过这个输入，如果是MAX_N*MAX_N的内存都会超内存
int len;
char chs[MAX_N];
inline int max(int a, int b) { return a > b? a : b; }
int tbl[2][MAX_N];

int longestPalindromeSequence()
{
	for (int i = 0; i < len; i++) tbl[0][i] = 1;
	bool id = false;

	for (int d = 2; d <= len; d++)
	{
		id = !id;
		for (int i = 0, j = i+d-1; j < len; i++, j++)
		{
			if (chs[i] == chs[j] && d == 2) tbl[id][i] = 2;
			else if (chs[i] == chs[j]) tbl[id][i] = tbl[id][i+1] + 2;
			else tbl[id][i] = max(tbl[!id][i], tbl[!id][i+1]);
		}
	}
	return tbl[id][0];
}

int main()
{
	while (~scanf("%d", &len))
	{
		getchar();	//Don't forget the last line's '\n' character.
		gets(chs);
		printf("%d\n", len - longestPalindromeSequence());
	}
	return 0;
}
  

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int MAX_N = 5001;//超过这个输入，如果是MAX_N*MAX_N的内存都会超内存 int len; char chs[MAX_N]; char revChs[MAX_N]; inline int max(int a, int b) { return a > b? a : b; } int tbl[2][MAX_N]; int longestCommonSequence() { memset(tbl[0], 0, sizeof(int)*(len+1)); tbl[1][0] = 0; bool id = false; for (int i = 0; i < len; i++) { id = !id; for (int j = 0; j < len; j++) { if (chs[i] == revChs[j]) tbl[id][j+1] = tbl[!id][j] + 1; else tbl[id][j+1] = max(tbl[!id][j+1], tbl[id][j]); } } return tbl[id][len]; } int main() { while (~scanf("%d", &len)) { getchar(); //Don't forget the last line's '\n' character. gets(chs); strncpy(revChs, chs, len); reverse(revChs, revChs+len); printf("%d\n", len - longestCommonSequence()); } return 0; }