05_最长回文子序列长度

一、测试输入：

abbcdecb

二、经转移公式推导：

三、测试程序

 1 /*
 2  *    最长回文子系列
 3  *
 4  */
 5 
 6 #include <stdio.h>
 7 #include <stdlib.h>
 8 #include <string.h>
 9 
10 #define MAX(a, b)    (a)>(b) ? (a):(b)
11 
12 int get_lps_len(unsigned char *str)
13 {
14     unsigned int len = 0;
15     int i = 0;
16     int j = 0;
17 
18     len = strlen(str);
19     int (*dp)[len] = (int (*)[len])malloc(sizeof(int)*len*len);
20     memset(dp, 0, sizeof(int)*len*len);
21 
22     for (i=len-1; i>=0; i--) {
23         dp[i][i] = 1;
24         for (j=i+1; j<len; j++) {
25             if (str[i] == str[j])
26                 dp[i][j] = dp[i+1][j-1] + 2;
27             else
28                 dp[i][j] = MAX(dp[i+1][j], dp[i][j-1]);
29         }
30     }
31 
32     for (i=0; i<len; i++) {
33         for (j=0; j<len; j++)
34             printf("%d ", dp[i][j]);
35         puts("");
36     }
37 
38     len = dp[0][len-1];
39     free(dp);
40 
41     return len;
42 }
43 
44 int main()
45 {
46     unsigned char str[1024] = {0};
47     
48     while (~scanf("%s", str))
49         printf("%d
", get_lps_len(str));
50 
51     return 0;
52 }