动态规划问题(二)

一、 最长公共子序列(二)

解法一:动态规划+递归(推荐)

• 优先检查特殊情况。
• 获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度。
• 遍历两个字符串的所有位置，开始状态转移：若是iii位与jjj位的字符相等，则该问题可以变成1+dp[i−1][j−1]，即到此处为止最长公共子序列长度由前面的结果加1。
• 若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i][j−1]或者dp[i−1][j]，我们取较大的一个就可以了，由此感觉可以用递归解决。
• 但是递归的复杂度过高，重复计算了很多低层次的部分，因此可以用动态规划，从前往后加，由此形成一个表，表从位置1开始往后相加，正好符合动态规划的转移特征。
• 因为最后要返回该序列，而不是长度，所以在构造表的同时要以另一个二维矩阵记录上面状态转移时选择的方向，我们用1表示来自左上方，2表示来自左边，3表示来自上边。
• 获取这个序列的时候，根据从最后一位开始，根据记录的方向，不断递归往前组装字符，只有来自左上的时候才添加本级字符，因为这种情况是动态规划中两个字符相等的情况，字符相等才可用。

class Solution {
    
public:
    string x = "";
    string y = "";
    //获取最长公共子序列
    string ans(int i, int j, vector<vector<int>>& b){
     
        string res = "";
        //递归终止条件
        if(i == 0 || j == 0)
            return res;
        //根据方向，往前递归，然后添加本级字符
        if(b[i][j] == 1){
    
            res += ans(i - 1, j - 1, b);
            res += x[i - 1];
        }
        else if(b[i][j] == 2)
            res += ans(i - 1, j, b);
        else if(b[i][j] == 3)
            res += ans(i,j - 1, b);
        return res;
    }
    string LCS(string s1, string s2) {
    
        //特殊情况
        if(s1.length() == 0 || s2.length() == 0) 
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        x = s1;
        y = s2;
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        //动态规划数组相加的方向
        vector<vector<int>> b(len1 + 1, vector<int>(len2 + 1, 0));
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; j++){
    
                //遇到两个字符相等
                if(s1[i - 1] == s2[j - 1]){
    
                    //考虑由二者都向前一位
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //来自于左上方
                    b[i][j] = 1;
                }
                //遇到的两个字符不同
                else{
    
                    //左边的选择更大，即第一个字符串后退一位
                    if(dp[i - 1][j] > dp[i][j - 1]){
    
                        dp[i][j] = dp[i - 1][j];
                        //来自于左方
                        b[i][j] = 2;
                    }
                    //右边的选择更大，即第二个字符串后退一位
                    else{
    
                        dp[i][j] = dp[i][j - 1];
                        //来自于上方
                        b[i][j] = 3;
                    }
                }
            }
        }
        //获取答案字符串
        string res = ans(len1, len2, b);
        //检查答案是否位空
        return  res != "" ? res : "-1";
    }
};

时间复杂度：O(n^2)，构造辅助数组dp与b，两层循环，递归是有方向的递归，因此只是相当于遍历了二维数组
空间复杂度:O(n^2) 辅助二维数组dp与递归栈的空间最大为O(n^2)

解法二:动态规划+栈

• 优先检查特殊情况。
• 获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度。
• 遍历两个字符串的所有位置，开始状态转移：若是iii位与jjj位的字符相等，则该问题可以变成1+dp[i−1][j−1]，即到此处为止最长公共子序列长度由前面的结果加1。
• 若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i][j−1]或者dp[i−1][j]，我们取较大的一个就可以了。
• 得到最长长度后，获取不需要第二个辅助数组b，直接从dp数组最后一位开始，每次比较当前位置与其左、上、左上的关系，然后将符合要求的字符加入栈中，符合要求即来自dp表格左上方的字符。
• 最后将栈中的字符拼接即可得到最长公共子序列，注意检查子序列是否为空·

class Solution {
    
public:
    string LCS(string s1, string s2) {
    
        //只要有一个空字符串便不会有子序列
        if(s1.length() == 0 || s2.length() == 0) 
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0)); 
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; 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]);
            }
        }
        //从动态规划数组末尾开始
        int i = len1, j = len2;
        stack<char> s;
        while(dp[i][j]){
    
            //来自于左方向
            if(dp[i][j] == dp[i - 1][j])
                i--;
            //来自于上方向
            else if(dp[i][j] == dp[i][j - 1])
                j--;
            //来自于左上方向
            else if(dp[i][j] > dp[i - 1][j - 1]){
    
                i--;
                j--;
                //只有左上方向才是字符相等的情况，入栈，逆序使用
                s.push(s1[i]); 
           }
        }
        string res = "";
        //拼接子序列
        while(!s.empty()){
    
            res += s.top();
            s.pop();
        }
        //如果两个完全不同，返回字符串为空，则要改成-1
        return res != "" ? res : "-1";  
    }
};

时间复杂度：O(n^2)最坏复杂度为构造辅助数组dp两层循环
空间复杂度：O(n^2) 辅助二维数组dp与栈空间最大为O(n^2)