首页 > 代码库 > 0804------算法笔记----------最长公共子序列
0804------算法笔记----------最长公共子序列
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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。