1159 POJ Palindrome

这道题的意思是对于给定字符串，至少插入多少个字符，可以变为对称字符串。

输入：
5      (字符串长度)
Ab3bd  (输入字符串)

输出：
2

可以证明：至少插入的字符数=字符换长度-源串和逆字符串的最长公共子串长度
下面可以把原题转换为求LCS问题。

首先，可以想到的是用递归的方法，但是递归方法是超时的。
所以要采用自底向上的方法，采用如下的递推公式：

c[i][j]= 0                                i=0或j=0
         c[i-1][j-1]+1                str[i-1]==inverstr[j-1]
         max{c[i-1][j],c[i][j-1]} str[i-1]!=inverstr[j-1]

结果会出现Runtime Error,因为字符串的长度最大是5000，要声明5000*5000的二维数组，肯定是会超的，这里需要采用滚动数组实现，因为c[i][j]仅仅和相邻的行和列有关，所以可以用2*5000的数组来实现。

具体代码如下：

#include<stdio.h>
#define MAXLEN 5005

void longestLength(char *Str,char *inverseStr,int len,int c[][MAXLEN])
{
  int i=0,j=0;
  //initial
  c[1][0]=0;c[0][0]=0;
  for(j=0;j<len;j++)
    c[i][j]=0;
  //begin from 1
  for(i=1;i<=len;i++)
  {
    for(j=1;j<=len;j++)
    {
      //滚动数组
      if(Str[i-1]==inverseStr[j-1])
        c[i%2][j]=c[(i-1)%2][j-1]+1;
      else if(c[(i-1)%2][j]>c[i%2][j-1])
        c[i%2][j]=c[(i-1)%2][j];
      else
        c[i%2][j]=c[i%2][j-1];
    }
  }
}
void inverse(char *Str,char *inverseStr,int len)
{
  int i=0;
  while(i<len){
    inverseStr[len-1-i]=Str[i];
    i++;
  }
  inverseStr[i]='\0';
}

int main(int argc,char **argv)
{
  char Str[MAXLEN];
  char inverseStr[MAXLEN];
  int c[2][MAXLEN];
  int len=0;  
  scanf("%d",&len);
  scanf("%s",Str);
  inverse(Str,inverseStr,len);
  longestLength(Str,inverseStr,len,c);
  printf("%d\n",len-c[len%2][len]);

}