If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
代码实现如下:
#include <stdio.h>
#include <string.h>
int max(int,int);
int palindrome(char*,int);
int main(void)
{
char string[]="character";
int length=strlen(string);
printf("%d",palindrome(string,length));
return 0;
}
int max(int a,int b)
{
return (a>=b)?a:b;
}
int palindrome(char* string,int length)
{
int log[length][length];
/*for(int i=0;i<length;i++)
for(int j=0;j<length;j++)
log[i][j]=0;*/
for(int i=length-1;i>=0;i--)
{
log[i][i]=1;
for(int j=i+1;j<length;j++)
{
if(string[i]==string[j])
log[i][j]=2+log[i+1][j-1];
else
log[i][j]=max(log[i][j-1],log[i+1][j]);
}
}
return log[0][length-1];
}