构成最小回文数的分析
给定字符串，可以通过插入字符，使其变成回文，求最少插入字符的数量。
比如
poj 1159 这题
Ab5db可以最少插入两个字符 构成回文 Abd5dbA
abcd可以最少插入三个字符 构成回文 abcdcba
分析：
用动态规划。
设字符为str[] ，长度为n，下标的开始为l，结束为h
那么如果str[l]==str[h] ，则只需要看str从l+1到h-1的回文如何构成
如果str[l]!=str[h]，那么要插入的字符要么跟str[l]相同，要么跟str[h]相同，假设：
跟str[l]相同，则只需判断l+1到h的字符如何构成回文
跟str[h]相同，则只需判断l到h-1的字符如何构成回文
由于是最少插入字符数，那么取上述两种情况中值最小的一种即可
递推公式为
f[l][h]=(str[l]==str[h])?f[l+1][h-1]:(min(f[l+1][h],f[l][h-1])+1)
下面是我的源代码，仅供参考：
#include<iostream>using namespace std;#define MAX 5005char str[MAX];short int fmi[MAX][MAX];inline int min(int a,int b){return a<b?a:b;}short int fmiDP(int N){int i,j,gap;for(i=0;i<MAX;i++)for(j=0;j<MAX;j++)fmi[i][j]=0;for(gap=1;gap<N;gap++) //core codefor(i=0,j=gap;j<N;i++,j++)fmi[i][j]=((str[i]==str[j])?fmi[i+1][j-1]:(min(fmi[i+1][j],fmi[i][j-1])+1));return fmi[0][N-1];}int main(){int N;while(cin>>N && N){cin>>str;cout<<fmiDP(N)<<endl;}return 0;}