動態規劃的經典應用，其實現在發現，其實質就是利用矩陣或者數組保存歷史結果，而不用每次遞歸求解
關鍵點：
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 閱讀(2504)
評論(1) 編輯 收藏 所屬分類:
算法