给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
思路：提到回文串，自然要利用回文串的特点，想到将源字符串逆转后，“回文串”（不一定连续）相当于顺序没变求原字符串和其反串的最大公共子序列（不是子串，因为可以不连续）的长度（使用动态规划很容易求得），然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。
1 #include2 #include 3 #include 4 using namespace std; 5 const int MAX = 1001; 6 int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法 7 int maxLen(string s1, string s2){ 8 int length1 = s1.size(); 9 int length2 = s2.size();10 for (int i = 0; i < length1; ++i)11 MaxLen[i][0] = 0;12 for (int i = 0; i < length2; ++i)13 MaxLen[0][i] = 0;14 15 for (int i = 1; i <= length1; ++i)16 {17 for (int j = 1; j <= length2; ++j)18 {19 if (s1[i-1] == s2[j-1]){20 MaxLen[i][j] = MaxLen[i-1][j - 1] + 1;21 }22 else23 {24 MaxLen[i][j] = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);25 }26 }27 }28 29 return MaxLen[length1][length2];30 }31 32 int main(){33 string s;34 while (cin >> s){35 int length = s.size();36 if (length == 1){37 cout << 1 << endl;38 continue;39 }40 //利用回文串的特点41 string s2 = s;42 reverse(s2.begin(),s2.end());43 int max_length = maxLen(s, s2);44 cout << length - max_length << endl;45 }46 return 0;47 }
动态规划参考：http://blog.csdn.net/yysdsyl/article/details/4226630/