题解 | #最长公共子序列-II#

最长公共子序列变型题
核心还是原题的思路，只不过加了需要求最终的子序列
时间复杂度：
空间复杂度：

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.length(), n = s2.length();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        int ans = 0; //最大长度
        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                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]);
                ans = max(ans, dp[i][j]);
            }
        }
        string res;
        int i = m, j = n;
        while(i > 0 && j > 0){ //逆序查找
            if(dp[i - 1][j - 1] == ans) i --, j --;
            else if(dp[i - 1][j] == ans) i --;
            else if(dp[i][j - 1] == ans) j --;
            else{
                ans --;
                res += s1[i - 1];
                i --, j --;
            }
        }
        reverse(res.begin(), res.end());
        return res == "" ? "-1" : res;
    }
};