poj1159

题目：Palindrome.

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.

实现代码如下：

#include <stdio.h>
#include <string>
//记忆化DFS
char str[5000+1];
short int dp[5000+1][5000+1];

int minx(int a,int b)   //注意别实现反了
{
    return a<=b?a:b;
}

int dfs(int left,int right)
{
    if(left>=right)
        return 0;

    if(dp[left][right]!=-1)
        return dp[left][right];
    else
    {
        if(str[left]==str[right])
             dp[left][right]=dfs(left+1,right-1);
        else
             dp[left][right]=minx(dfs(left+1,right),dfs(left,right-1))+1;
        
        return dp[left][right];
    }
}

int main()
{
    int len;
    while(~scanf("%d",&len))
    {
        scanf("%s",str);
        memset(dp,-1,sizeof(dp));
        printf("%d\n", dfs(0,len-1));
    }
    return 0;
}