首页 > 代码库 > 0804------算法笔记----------最长公共子序列

0804------算法笔记----------最长公共子序列

2024-07-15 19:36:05   212人阅读

1.动态规划和子序列

　　1.1 动态规划的特征：

　　　　a）最优子结构，求问题的解必须获取子问题的最优解；

　　　　b) 重叠子问题，使用原始的递归存在大量的重复计算。

　　1.2 子序列的概念：

　　　　a）子序列中的元素都是原字符串中的元素；

　　　　b）子序列中元素的排列顺序，与他们在原字符串中的顺序相一致；

　　　　c）子序列不同于子串，子序列中额元素在原字符串中未必是连续的。

　　　　e）eg.src = "http://www.mamicode.com/foobar" ,那么 "fbr" 就是一个子序列。

2.求最长公共子序列的三个版本

　　2.1 最原始的递归求解，没有考虑重复计算问题。

#include <iostream>#include <string>using namespace std;int LCS(const string &str1, const string &str2, int i, int j);int main(int argc, const char *argv[]){    string str1 = "ABCBDAB";    string str2 = "BDCABA";    cout << LCS(str1, str2, str1.size(), str2.size()) << endl;    return 0;}// i j 表示长度，即str1的前i个字节 和 str2的前j个字节int LCS(const string &str1, const string &str2, int i, int j){    if(i == 0 || j == 0)        return 0;    if(str1[i-1] == str2[j-1]){        return LCS(str1, str2, i-1, j-1)+1;    }    else{        int ret1 = LCS(str1, str2, i-1, j);        int ret2 = LCS(str1, str2, i, j - 1);        return  ret1 > ret2 ? ret1 : ret2 ;    }}

　　2.2 画出上述递归树可以看到，大量的分支是重复的，那么重复的计算是否可以避免？显然可以，这里将所有的计算都存储在数组中，那么计算过的值就不会计算第二次，效率会大大提高。

#include <iostream>#include <string>#include <string.h>using namespace std;int memo[100][100];//全局数组 存储已经计算过的LCS[i][j]int LCS(const string &str1, const string &str2, int i, int j);int main(int argc, const char *argv[]){    string str1 = "ABCBDAB";    string str2 = "BDCABA";    memset(memo, -1, sizeof memo);    cout << LCS(str1, str2, str1.size(), str2.size()) << endl;    return 0;}// i j 表示长度，即str1的前i个字节 和 str2的前j个字节int LCS(const string &str1, const string &str2, int i, int j){    if(memo[i][j] != -1)        return memo[i][j];    if(i == 0 || j == 0)        return 0;    if(str1[i-1] == str2[j-1]){        memo[i][j] = LCS(str1, str2, i-1, j-1) + 1;        return memo[i][j];    }    else{        int ret1 = LCS(str1, str2, i-1, j);        int ret2 = LCS(str1, str2, i, j - 1);        memo[i][j] = ret1 > ret2 ? ret1 : ret2;        return memo[i][j];    }}

　　2.3 非递归方法。从串长度为 0 开始依次求解，这里可作图研究，执行的过程就是填充一个二维数组的过程。

#include <iostream>#include <string>#include <stdlib.h>#include <string.h>using namespace std;/* * 最长公共子串 */int main(int argc, const char *argv[]){    if(argc != 3){       cout << "Too Few Arguments" << endl;       exit(EXIT_FAILURE);    }    string str1 = argv[1];    string str2 = argv[2];    int memo[100][100];    memset(memo, -1, sizeof memo);    int i, j;    for(i = 0; i <= str1.size(); i++)        for(j = 0; j <= str2.size(); j++){            if(i == 0 | j == 0)                memo[i][j] = 0;            else{                if(str1[i-1] == str2[j-1])                    memo[i][j] = memo[i-1][j-1] + 1;                else                    memo[i][j] = memo[i-1][j] > memo[i][i-1] ? memo[i-1][j] : memo[i][j-1];            }        }    cout << memo[str1.size()][str2.size()] << endl;    return 0;}

　　

 


联系
我们