动态规划的经典应用，其实现在发现，其实质就是利用矩阵或者数组保存历史结果，而不用每次递归求解
关键点：
1.找出问题的
递归表达式
2.然后根据表达式，直接转化为
矩阵上的数据运算
本问题的递归表达式为：
L［i,j］等于 0 ifi＝0 或者 j＝0
等于L［i-1,j-1］＋1 ifi>0 ,j>0 ai = bi
等于 max｛L［i,j-1］, L［i-1,j］｝ if i > 0 j>0, ai != bj
纯c实现
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define MAXSIZE 10
4 static char * LCSarray;
5 static char *start; //指向LCSarray数组中最长公共字串的开始位置
6 int findLCS(char*, int, char*, int );
7
8 int main()
9 {
10 char * a = "0xyxxzxyzxy"; //第一位都没有意义
11 char *b = "0zxzyyzxxyxxz";
12
13 LCSarray = (char *)malloc(sizeof(char)*MAXSIZE);//保存最长公共字串的数组容器
14 int LCSNum = findLCS(a,10, b, 12);
15 printf("the result is: %d \n", LCSNum );
16 printf("the result char is: %s \n", start );
17
18 free(LCSarray);
19 exit(EXIT_SUCCESS);
20 }
21
22 int findLCS(char * a, int na, char *b, int nb)
23 {
24 int i = 0, j = 0; //i代表行下标j代表列下标
25 int t = 0; //保存最长公共字串的下标
26
27 //以下构建矩阵
28 int ** matrix = (int **)malloc(sizeof(int *) * (na + 1));
29 for(i =0; i <na+1; i++)
30 matrix[i] = (int *) malloc(sizeof(int) * (nb +1));
31 //把第一行第一列都初始化为0
32 for(j = 0; j < nb +1; j++)
33 {
34 matrix[0][j] = 0;
35 }
36 for(i = 0; i < na +1; i++)
37 {
38 matrix[i][0] = 0;
39 }
40 //填该矩阵，即求解
41 for(i = 1; i < na + 1; i++)
42 {
43 for(j = 1; j < nb + 1; j++)
44 {
45 if(a[i] == b[j])
46 {
47 matrix[i][j] = matrix[i-1][j -1] + 1;
48 }
49 else
50 matrix[i][j] =matrix[i-1][j]>matrix[i][j-1]?matrix[i-1][j]:matrix[i][j-1];
51 }
52
53 }
54 //找出一个最大公共字串(一开始还以为是条捷径呢，原来是谬误，
55 //因为只考虑最后一列比较，你不能确定较大值必定包含在全局的最大公共子序列中)
56 // int max = 0;
57 // for(i = 1; i < na +1; i++)
58 // {
59 // if(matrix[i][nb] > max)
60 // {
61 // LCSarray[t++] = a[i];
62 // max = matrix[i][nb];
63 // }
64 // }
65 /*从matrix尾部纵向优先搜索，碰到两个不同值时保存char，一直到第一行（其实最合理的应该最后搜索到matrix[1][1]节点）*/
66 i = na;
67 j = nb;
68 char * p = LCSarray + MAXSIZE-1; //指向尾部
69 * p = '\0';
70 while(i>0) //纵向搜索
71 {
72 while(matrix[i][j] == matrix[i-1][j])
73 {
74 i--;
75 };
76 *--p = a[i];
77 i--;
78 j--;
79 }
80 start = p;
81 //矩阵最后一个元素即是我们所需的最长公共子序列的个数
82 int result = matrix[na][nb];
83 //释放空间
84 for(i =0; i <na+1; i++)
85 free(matrix[i]);
86 free(matrix);
87 return result;
88 }
posted on 2008-04-06 22:51
fullfocus 阅读(2499)
评论(1) 编辑 收藏 所属分类:
算法