// C++ 用一个dp数组记录最终string结果 ，内存会超 string LCS(string s1, string s2) { // write code here vector<vector><string>> dp(s1.size(), vector<string>(s2.size(), "")); for (int i1 = 0; i1 < s1.size(); ++i1) { if (s1[i1] == s2[0]) { dp[i1][0] = s1[i1]; } } for (int i2 = 0; i2 < s2.size(); ++i2) { if (s2[i2] == s1[0]) { dp[0][i2] = s2[i2]; } } for (int i1 = 1; i1 < s1.size(); ++i1) { for (int i2 = 1; i2 < s2.size(); ++i2) { if (s1[i1] == s2[i2]) { dp[i1][i2] = dp[i1 - 1][i2 - 1] + s1[i1]; }else { if (dp[i1 - 1][i2].size() > dp[i1][i2 - 1].size()) { dp[i1][i2] = dp[i1 - 1][i2]; } else { dp[i1][i2] = dp[i1][i2 - 1]; } } } } if (dp[s1.size() - 1][s2.size() - 1] == "") return "-1"; return dp[s1.size() - 1][s2.size() - 1]; }</string></string></vector>