声明:算法学习来自,7月算法,面试&算法&机器学习&找工作就上七月算法
1. 今天学习的算法是 LCS,最长公共子序列,属于典型的动态规划基础题。
十分钟搞定LCS 学习视频:http://julyedu.com/video/play/id/9
2. 实践代码:
/* Algorithm LCS */ #include <stack> #include <cstdio> #include <string> #include <iostream> #include <algorithm> using namespace std; #define MAX 50 // Get LCS int 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 string string PrintLcs(int path[][MAX], const string& strOne, const string& strTwo) { stack <char> 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; }
时间: 2024-10-23 19:59:52