本文共 1646 字，大约阅读时间需要 5 分钟。
声明：算法学习来自，7月算法，面试&算法&机器学习&找工作就上七月算法
1. 今天学习的算法是 LCS，最长公共子序列，属于典型的动态规划基础题。
十分钟搞定LCS 学习视频：http://julyedu.com/video/play/id/9
2. 实践代码：
/*Algorithm LCS*/#include#include #include #include #include using namespace std;#define MAX 50// Get LCSint GetLcs(int dp[][MAX], int path[][MAX], const string& strOne, const string& strTwo) { int strOneLength = strOne.length(); int strTwoLength = strTwo.length(); for (int i = 0; i < strOneLength; ++i) { dp[i][0] = 0; } for (int i = 0; i < strTwoLength; ++i) { dp[0][i] = 0; } for (int i = 0; i < strOneLength; ++i) { for (int j = 0; j < strTwoLength; ++j) { if (strOne[i] == strTwo[j]) { dp[i+1][j+1] = dp[i][j] + 1; path[i+1][j+1] = 0; //leftTop } else { if (dp[i][j+1] > dp[i+1][j]) { dp[i+1][j+1] = dp[i][j+1]; path[i+1][j+1] = -1; //top } else { dp[i+1][j+1] = dp[i+1][j]; path[i+1][j+1] = 1; //left } } } } return dp[strOneLength][strTwoLength];}// Print LCS stringstring PrintLcs(int path[][MAX], const string& strOne, const string& strTwo) { stack stk; int i = strOne.length(); int j = strTwo.length(); while ((i > 0) && (j > 0)) { if (path[i][j] == 0) { stk.push(strOne[i-1]); --i; --j; } else if (path[i][j] == 1) { --j; } else { --i; } } string lcsString = ""; while (!stk.empty()) { lcsString = lcsString + stk.top(); stk.pop(); } return lcsString;}int main(int argc, char **argv) { string strOne = "bdcaba"; string strTwo = "abcbdab"; int dp[MAX][MAX], path[MAX][MAX]; cout << GetLcs(dp, path, strOne, strTwo) << endl; cout << PrintLcs(path, strOne, strTwo) << endl; return 0;}
转载地址：http://gyato.baihongyu.com/