A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome
input：
Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct
output：
Your program is to write to standard output. The first line contains one integer, which is the desired minimal number
input：
5
Ab3bd
output：
2
题目翻译：
回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到 左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文 词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。 比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词(“dAb3bAd” “Adb3bdA”)。
分析：就是把输入的字符串倒序和原串求最长公共子序列，原理见我的上一篇解析，原理差不多。
【参考程序】：
#include<iostream>
#include<cstring>
using namespace std;
string s1,s2;
short f[5001][5001];
int n;
int main()
{
scanf("%d",&n);getchar();
getline(cin,s1);s1=' '+s1;
s2=' ';
for (int i=n;i>=1;i--) s2+=s1[i];
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
else
{
if (f[i-1][j]>f[i][j-1])
f[i][j]=f[i-1][j];
else f[i][j]=f[i][j-1];
}
printf("%d\n",n-f[n][n]);
return 0;
}