POJ 1159--Palindrome(回文序列)

题目要求对于一序列至少加上多上字符能组成一个回文序列，可参考算法导论中LCS的DP证明方法。

设序列为a[i]，b[i][j]为a[i]到a[j]组成的子串插入最少的字符构成的回文序列，设dp[i][j]为最少需要插入字符的数目。

首先证明b[i][j]的始终字符(肯定相同)必定是a[i]，a[j]当中其中一个。

反证：若始终字符为x0，b[i][j] = x0 x1 ...xk a[i] ...a[i] xk ... x1 x0或者x0 x1 .. xk a[j] a[i] .. a[i] a[j] xk .. x1 x0，则我们剥离所有x字符，组成的序列是一个需要插入字符更少的b[i][j]，矛盾。

#include<cstdio>
#include<cstring>
#define maxN 6001
#define _min(x,y) ((x)<(y)?(x):(y))

int main()
{
    int i,j,N;
    char flag;
    char str[maxN];
    short minNum[2][maxN];
    while(~scanf("%d",&N))
    {
        getchar();
        gets(str);
        memset(minNum,0,sizeof(minNum));
        flag = 1;
        for(i = N-1;i >= 0;i--)
        {
            for(j = i+1;j < N;j++)
            {
                if(str[i] == str[j])
                    minNum[flag][j] = minNum[!flag][j-1];
                else
                    minNum[flag][j] = _min(minNum[!flag][j],minNum[flag][j-1])+1;
            }
            flag = !flag;
        }
        printf("%d\n",minNum[!flag][N-1]);
    }
    return 0;
}