思路

长度很容易计算，如果遇到相同字母就是 dp[i-1][j-1]+1; 如果不同，则是 max(dp[i-1][j], dp[i][j-1])

path: 1 左上，2 左，3 上 然后递归回溯，回溯的时候别弄错左/上对应的 id。

• end: 0,0 = ""
• case1：+str2[j-1] 更新

code

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */

    string dfs(int i, int j, string& str2, vector<vector<int>>& path) {
        if (i == 0 || j == 0) { return "";}
        switch(path[i][j]) {
            case 1: return dfs(i-1, j-1, str2, path) + str2[j-1]; // j-1！！！！！！
            case 2: return dfs(i-1, j, str2, path);
            case 3: return dfs(i, j-1, str2, path);
        }
        return "";
    }

    string LCS(string str1, string str2) {
        // write code here
        int n1 = str1.length(), n2 = str2.length();

        vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        for (int i = 0; i <= n1; ++i) { dp[i][0] = 0;}
        for (int i = 0; i <= n2; ++i) { dp[0][i] = 0;}

        vector<vector<int>> path(n1+1, vector<int>(n2+1, 0));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (str1[i-1] == str2[j-1]) { 
                    dp[i][j] = dp[i-1][j-1] + 1;
                    path[i][j] = 1; // 左上
                }
                else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                    if (dp[i-1][j] > dp[i][j-1]) { path[i][j] = 2;} // 上
                    else { path[i][j] = 3;} // 左
                }
            }
        }
        cout << dp[n1][n2] << endl;
        string ans = "";
        ans = dfs(n1, n2, str2, path);
        if (ans.empty()) { return "-1";}
        return ans;
    }
};