代码随想录算法训练营打卡Day53 | LeetCode1143 最长公共子序列、LeetCode1035 不相交的线、LeetCode53 最大子数组和

摘要

如果不要求子序列中的元素在原序列中连续，相比于要求“连续”，dp数组的定义和递推公式是不一样的。
如果要求“连续”，那dp数组定义为以具体的元素结尾；如果不要求连续，那么dp数组定义为尝试到对应元素。

LeetCode1143 最长公共子序列

1143. 最长公共子序列 - 力扣（Leetcode）

在代码随想录算法训练营打卡Day52中的最后一题，简单地分析了一下如何通过dp数组的定义和递推公式来保证子序列中的元素在原序列中连续，那不要求“连续”要怎么做呢？这就是本题的要求。
本题只要求子序列中的元素保持在原序列中的相对顺序，不要求连续分布。
dp数组及数组下标的含义：dp[i][j]表示，text1的子序列中的元素的下标属于[0, i-1]，text2的子序列中的元素的下标属于[0, j-1]，这两个子序列的公共部分的长度为dp[i][j]。
- 可以这么理解，就是尝试到了text1[i-1]和text2[j-1]的子序列，可以选择text1[i-1]和text2[j-1]的子序列，但text1[i-1]和text2[j-1]不一定是子序列的结尾。
那么递推公式也好理解了，dp[i][j]有三种更新的可能，dp[i][j]的更新对应着当前比对的元素为text1[i-1]和text2[j-1]
- 当前尝试到text1[i-1]，如果不选text1[i-1]，那么dp[i][j]=dp[i-1][j]
- 当前尝试到text2[j-1]，如果不选text2[j-1]，那么dp[i][j]=dp[i][j-1]
  - 以上两种情况相当于``text1[i-1] != text2[j-1]，公共子序列的长度没有增加，这两种情况组合起来其实也就包含了不选text1[i-1]和text2[j-1]`都不选情况。
- 如果text1[i-1] == text2[j-1]，说明公共子序列的长度可以增加，增加之前的最长公共子序列的长度是dp[i-1][j-1]，新增一个公共元素，dp[i][j]=dp[i-1][j-1]。
- 递推公式
$dp[i][j]= \begin{cases} max(dp[i-1][j], dp[i][j-1]),& text1[i-1] \ne text[j-1] \\ dp[i-1][j-1] + 1,,& text1[i-1] == text[j-1] \end{cases}$

遍历顺序：dp[i][j]更新依赖的状态都是i-1或j-1，所以i和j都是从小到大遍历。

初见的题解代码如下

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        int res = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); 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 - 1], max(dp[i - 1][j], dp[i][j - 1]));
                res = max(res, dp[i][j]);
            }
        }

        return res;
    }
};

实际上，正如之前所分析的，不需要再比较dp[i-1][j-1]，因为dp[i-1][j]和dp[i][j-1]就包含了dp[i-1][j-1]的情况

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        int res = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); 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]);
                res = max(res, dp[i][j]);
            }
        }

        return res;
    }
};

根据dp数组的定义，实际上也不需要再在dp数组的更新过程中维护一个最大值，dp[text1.size()][text2.size()]相当于已经比对完了所有元素，它的值就是答案。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        // int res = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); 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]);
                // res = max(res, dp[i][j]);
            }
        }

        return dp[text1.size()][text2.size()];
    }
};

以 LeetCode 的示例一为例来模拟dp数组的更新过程

LeetCode1035 不相交的线

1035. 不相交的线 - 力扣（Leetcode）

复制上一题的题解代码，查找并替换，提交通过。

开个玩笑，但这道题目如果用动态规划的思路来解决，几乎是和上一题一样的。只是这道题目是用具体情形来描述问题的，需要我们从具体的情形中抽象出一个“最长公共子序列”的问题。
- 首先要找到可以连接的元素，实际上就是在找nums1和nums2中元素的交集，那问题来了，这种求集合的问题一般都要明确是求组合还是求排列，这题要求什么？接着看题目的要求。
- 找一个nums1的子集与一个nums2的子集，这两个子集中的元素相同，并且要保证各组相同元素之间连线不能相交。怎么保证各组相同元素之间的连线不相交呢？
- 假设前面已经连好了一组，nums1[i]和nums2[j]相连，再连一条线，假设是nums1[a]和nums2[b]相连：
  - 如果 $a < i \ \wedge \ j < b$ 或 $i < a \ \wedge \ b < j$ ，如下图，那么连线一定会相交

只有 $a < i \ \wedge \ b < j$ 或 $i < a \ \wedge \ j < b$ ，如下图，连线才不会相交

这告诉我们，nums1的子集中的元素和nums2中子集中的元素，要保持在原序列中的相对顺序，即选取出的子集中的元素下标应该是严格递增的。所以，就是要求一个nums1的子序列和一个nums2的子序列，这两个子序列相等，且长度尽可能长。就是求最长公共子序列。

题解代码如下

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        // int res = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); 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]);
                // res = max(res, dp[i][j]);
            }
        }

        return dp[nums1.size()][nums2.size()];
    }
};

LeetCode53 最大子数组和

这道题目之前用贪心法写过，贪心策略为：如果当前子数组的和大于0，就继续累加；如果当前子数组的和大于之前记录过的最大值，就更新最大值；如果当前子数组的和小于0，说明之前确定的子数组的起始下标和终止下标不合适，以i+1作为新的起始下标。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur += nums[i];
            if (cur > res) res = cur;
            if (cur < 0) cur = 0;
        }
        return res;
    }
};

那么用动态规划的思想，怎么解决这道题呢？
首先，本题要求“连续”，根据之前的经验，在定义dp数组和推导递推公式时需要注意。
确定dp数组及数组下标的含义：本题要求“连续”，所以这样定义dp数组——dp[i]表示以nums[i]结尾的连续子数组的元素之和的最大值。
递推公式，对于dp[i]，其可能有两种更新来源，当前的子数组以nums[i]结尾
- 接上之前以nums[i-1]为结尾的子数组能得到最大和，那么根据dp数组的定义，之前0到i-1的最大和为dp[i-1]，所以dp[i] = dp[i-1] + nums[i]。
- 不接上之前以nums[i-1]为结尾的子数组能得到最大和，那么根据dp数组的定义，以nums[i]结尾的子数组只能是只有nums[i]自身，所以dp[i] = nums[i]
- 当然是取两种情况的最大值 $dp[i] = max(nums[i], dp[i - 1] + nums[i])$
本题的初始化可以将dp[i]统一初始化成nums[i]，但实际上更新dp数组时也会覆盖一次初始值，所以无所谓其他dp值得初始化。只要初始化dp[0]=nums[0]即可。
遍历顺序，dp[i]依赖于dp[i-1]，i从小到大遍历。

题解代码如下

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), INT_MIN);
        dp[0] = nums[0];

        int res = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            res = max(res, dp[i]);
        }

        return res;
    }
};

代码随想录算法训练营打卡Day53 | LeetCode1143 最长公共子序列、LeetCode1035 不相交的线、LeetCode53 最大子数组和

代码随想录算法训练营打卡Day53 | LeetCode1143 最长公共子序列、LeetCode1035 不相交的线、LeetCode53 最大子数组和

摘要

LeetCode1143 最长公共子序列

LeetCode1035 不相交的线

LeetCode53 最大子数组和

相关阅读更多精彩内容

友情链接更多精彩内容