【Day38 LeetCode】动态规划DP 子序列问题Ⅱ

确定dp数组含义，dp[i][j]表示长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列的长度。
dp转移关系，对于当前值dp[i][j], 分为text1[i - 1] 与 text2[j - 1]相同与不相同两种情况。text1[i - 1] 与 text2[j - 1]相同时，这两个字符可以作为最长公共子序列的一部分，$dp[i][j]=dp[i-1][j-1]+1$；text1[i - 1] 与 text2[j - 1]不同时，从不要text1[i-1]或者text2[j-1]中选取最大值，$dp[i][j]=max(dp[i][j-1],dp[i-1][j])$。
边界的初始值都为0，因为还没有公共子序列。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

从递推公式来看，当前的dp值dp[i][j]只与上方、左方和左上方的值有关，可以进一步优化空间复杂度。只与上方和左方有关，之前的博客介绍过优化的写法，这题多了一个左上方的值，如果只采用一维数组，那么左上方的值会被左方的值更新替代，所以需要额外的变量来存储和更新当前值的左上方值。
同时，将二维数组优化成一维数组时，还需要注意边界和初始化的问题。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<int> dp(n + 1);
        for(int i=1; i<=m; ++i){
            int leftup = dp[0];
            for(int j=1; j<=n; ++j){
                int tmp = dp[j];
                if(text1[i-1]==text2[j-1]){
                    dp[j] = leftup + 1;
                }else{
                    dp[j] = max(dp[j], dp[j-1]);
                }
                leftup = tmp;
            }
        }
        return dp[n];
    }
};

这题也是有两个容器，只不过由字符串变成了整型数组。仍可套用相似的dp数组定义。
对于递推关系的推导，也可分为nums1[i-1]与nums2[j-1]相同和不相同，对于相同的情况，这两个数可以画一条线，所以$dp[i][j]=dp[i-1][j-1]+1$；对于不同的情况，这两明确不能画线，则可以从dp[i-1][j]、dp[i][j-1]取最大值，的$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$。可以发现，递推公式与上一题也一样。
初始化也是，边界都初始化为0，因为不能画出线。
代码如下，这题和上一题可以说是一模一样。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

空间复杂度优化也是一样的，甚至代码都一模一样，就不赘述了。

dp数组dp[i]表示下标0~i（以nums[i]为结尾）的最大连续子序列和，递推公式为$dp[i]=max(nums[i],nums[i]+dp[i-1])$

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int ans = nums[0];
        for(int i=1; i<n; ++i){
            dp[i] = max(nums[i], nums[i] + dp[i-1]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

发现当前值dp[i]只与dp[i-1]有关，所以可以只采用变量来替代数组，优化空间复杂度，代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0], cur = nums[0];
        for(int i=1; i<nums.size(); ++i){
            cur = max(nums[i], nums[i] + cur);
            ans = max(ans, cur);
        }
        return ans;
    }
};

有两个字符串，想到dp数组含义dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。
递推公式，对于当前dp[i][j]，分为s[i-1]与t[j-1]相等和不相等两种情况。当s[i-1]==t[j-1]，则$dp[i][j]=dp[i-1][j-1]$；当s[i-1]!=t[j-1]时，需要将这个不等的元素删掉，$dp[i][j]=dp[i][j-1]$

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i=0; i<=n; ++i)
            dp[0][i] = 1;
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        vector<int> dp(n+1, 1);
        for(int i=1; i<=m; ++i){
            int leftup = dp[0];
            dp[0] = 0;
            for(int j=1; j<=n; ++j){
                int tmp = dp[j];
                if(s[i-1] == t[j-1]){
                    dp[j] = leftup;
                }else{
                    dp[j] = dp[j-1];
                }
                leftup = tmp;
            }
        }
        return dp[n];
    }
};

也可以采用双指针的方法，使用两个指针指向两个字符串，子序列的指针碰到相等的值才移动，空间复杂度更低。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        int j = 0; // 指向s的指针
        for(int i=0; i<t.size(); ++i){
            if(t[i] == s[j])
                ++j;
            if(j==n)
                return true;
        }
        return n==0;
    }
};