算法导论笔记:15-2 最长回文子序列

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];
}