题解 | #最长公共子序列-II# 学会如何逆向求res

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    /*
    dp(i,j)
    */
    string LCS(string s1, string s2) {
        int len1 = s1.size(), len2 = s2.size();
        if (len1 == 0 || len2 == 0) {
            return "-1";
        }
        vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));
        for(int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    if (s1[i-1] == s2[j-1]) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
        }
        // 逆推res
        string res = "";
        for (int i = len1, j = len2; 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;
        // write code here
    }
};