pku1159 Palindrome

解题思路：

amount(i,j)代表字符序列从i到j需要插入的个数

 

#include<stdio.h>


char g[5001];
short amount[5000][5000];

short min(short x,short y)
{
    return x>y?y:x;
}

int main()
{
    int n;
    scanf("%d%s",&n,g);
    for(int i=n-1;i>=0;i--)
    {
        for(int j=i;j<n;j++)
        {
            if(g[i]==g[j])
            {
                amount[i][j]=amount[i+1][j-1];
            }else
            {
                amount[i][j]=1+min(amount[i+1][j],amount[i][j-1]);
            }
        }
    }
    printf("%d\n",amount[0][n-1]);
    return 0;
}