题解 | #最长公共子序列-II#(动态规划且得到字符串结果)
最长公共子序列-II
http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
- dp[i][j]:str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列
- 初始化:dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0
-
- 根据dp,从后往前,查找结果。
class Solution { /* dp[i][j]:str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列 初始化:dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0 dp[i][j] = dp[i-1][j-1] + 1 当(s1[i-1] == s2[j-1])时。 max(dp[i-1][j], dp[i][j-1]); others 根据dp,从后往前,查找结果。 */ public: string LCS(string s1, string s2) { if(s1.empty() || s2.empty()) return "-1"; // 边界 int dp[s1.size()+1][s2.size()+1]; // dp数组 // 初始化 for(int i = 0; i <= s1.size(); i++) dp[i][0] = 0; for(int j = 0; j <= s2.size(); j++) dp[0][j] = 0; for(int i = 1; i <= s1.size(); i++) { for(int j = 1; j <= s2.size(); j++) dp[i][j] = (s1[i-1] == s2[j-1]) ? dp[i-1][j-1] + 1: max(dp[i-1][j], dp[i][j-1]); } string res = ""; for(int i = s1.size(), j = s2.size(); dp[i][j] >= 1;) { if(s1[i-1] == s2[j-1]) { res += s1[i-1]; i--;j--; } else if(dp[i-1][j] >= dp[i][j-1]) i--; else j--; } reverse(res.begin(), res.end()); return res.empty() ? "-1" : res; } };