算法设计------Dynamic Pragraming Longest Common Subsequence

发表于 | 分类于

问题描述

给定两个序列，找出它们中最长的子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“abc”，“abg”，“bdf”，“aeg”，“”acefg“等等是”abcdefg“的子序列。所以一个长度为n的字符串有2 ^ n个不同的子序列。

例如：
“ABCDGH”和 “AEDFHR” 的LCS是“ADH” 长度为3
“AGGTAB”和 “GXTXAYB”的LCS是“GTAB” 长度为4

问题分析

设Dij为x1…i 和y1…j的LCS的长度。

  • 初始情况：
    Di0 = D0j = 0;
  • 如果 xi = yj,则
    Dij = Di−1,j−1 + 1
  • 否则，xi 和 yi 都不存在于LCS，所以Dij可表示为
    Dij = max{ Di-1,j , Di,j-2 }

Coding

递归实现

1
2
3
4
5
6
7
8
9
10
int lcs(char * x , char * y ,int x_length, int y_length){
    if (x_length == 0 || y_length == 0) {
        return 0;
    }
    if (x[x_length - 1] == y[y_length -1]) {
        return lcs(x, y, x_length - 1, y_length -1) + 1;
    }else{
        return MAX(lcs(x, y, x_length - 1, y_length), lcs(x, y, x_length, y_length - 1));
    }
}

时间复杂度

递归实现的时间复杂度为2^n ,最坏情况为，当x，y的所有字符均不匹配时。

动态规划法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lcs(char * x , char * y ,int x_length, int y_length){
    int lcs_length[x_length + 1][y_length + 1];
    int i , j;
    for (i = 0; i <= x_length; i ++) {
        
        for (j = 0; j <= y_length; j ++) {
            if (i == 0 || j == 0) {
                lcs_length[i][j] = 0;
            }else if (x[i - 1] == y[j - 1]) {
                lcs_length[i][j] = lcs_length[i - 1][j - 1] + 1;
            }else{
                lcs_length[i][j] = MAX(lcs_length[i][j - 1], lcs_length[i - 1][j]);
            }
        }
    }
    return lcs_length[x_length][y_length];
}

时间复杂度

时间复杂度为 m * n;

测试代码

1
2
3
4
char * x = "AGGTAB";
char * y = "GXTXAYB";
int lcs_length = lcs(x, y, 6, 7);
printf("lcs_length == %d\n",lcs_length);

Output

1
lcs_length == 4

如果对你有帮助的话，Star✨下一吧！