Palindrome Time Limit:3000MS Memory Limit:65536K
Total Submit:12142 Accepted:4213
Description 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.
Sample Input
5Ab3bd
Sample Output
2
Source
IOI 2000
分析：
動態規劃求解。
設ch[1]..ch[n]表示字符串1至n位，i為左游標，j為右游標 ，則i從n遞減，j從i開始遞增。
min[i][j]表示i和j之間至少需要插入多少個字符才能對稱,我們最終需要得到的值是min[1][n].
則
if(ch[i]==ch[j])
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 + （min[i+1][j]和min[i][j-1]中的較小值）;
另外，min[][]可以定義為short 而非 int,動態規劃算法通常緊缺memory 。
什么？你說short 和 int是一樣的？ 呵呵，兄弟，大概你看的是年代比較久遠的C語言教材吧～
1
#include "string.h"
2#include "stdio.h"
3 int min[5001][5001];
4
5int MIN(short a,short b)
6
{
7
if(a>b)return b;
8 else return a;
9
}
10
11int main()
12{
13 int n;
14 int i,j;
15 char ch[5001];
16
17
18 scanf("%d",&n);
19 scanf("%s",ch+1);
20 for(i=1;i<=n;i++)
21 for(j=1;j<=n;j++)
22 min[i][j]=0;
23
24 for(i=n-1;i>=0;i--)
25 for(j=i;j<=n;j++)
26 if(ch[i]==ch[j])min[i][j]=min[i+1][j-1];
27 else min[i][j]= 1 + MIN(min[i+1][j],min[i][j-1]);
28 printf("%d",min[1][n]);
29
30return 0;
31
32}