代码随想录算法训练营Day50|1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列

最长公共子序列

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

代码随想录 (programmercarl.com)

最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili

本题和上一题718.最长重复子数组在很多方面相似，区别在与不需要连续，因此在dp数组的推导上有些改变。

由于不需要连续，dp[i][j]的值针对text1和text2相同及不同这两种情况有不同的表示。

首先 dp[i][j]表示序列text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度

当text[i-1] == text[j-1]时，dp[i][j] = dp[i-1][j-1]+1，而当text1[i-1]!=text2[j-1]时，dp[i][j] = max(dp[i-1][j],dp[i][j-1])，dp[i][j]由数组左和上的较大值确定。

由此，dp[i][j]由左上部分确认，当i j为0时，表示的序列为空，空序列与任何序列的最长公共子序列均为空，长度为0，dp[0][0]、dp[0][1]、dp[1][0]都为0。

i，j两个变量循环遍历。

最后返回dp[text1.size()][text2.size()]。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 创建一个二维向量 dp，用于存储动态规划的状态值// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度// 初始化 dp 的大小为 (text1.size()+1) x (text2.size()+1)，值全部为 0vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));// 双层循环遍历 text1 和 text2for (int i = 1; i <= text1.size(); i++) {  // i 从 1 开始，直到 text1.size()for (int j = 1; j <= text2.size(); j++) {  // j 从 1 开始，直到 text2.size()// 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同if (text1[i - 1] == text2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前字符不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[text1.size()][text2.size()]，即 text1 和 text2 的 LCS 长度return dp[text1.size()][text2.size()];}

算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)，m和n分别代表两个序列的长度，二维数组，二维循环遍历。

不相交的线

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

和上题一致，换些变量便能解决，不过真要面试的时候，希望能想到吧。

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 创建一个二维向量 dp，用于存储动态规划的状态值// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的最长公共子序列的长度// 初始化 dp 的大小为 (nums1.size()+1) x (nums2.size()+1)，值全部为 0vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));// 双层循环遍历 nums1 和 nums2for (int i = 1; i <= nums1.size(); i++) {  // i 从 1 开始，直到 nums1.size()for (int j = 1; j <= nums2.size(); j++) {  // j 从 1 开始，直到 nums2.size()// 如果 nums1 的第 i 个元素和 nums2 的第 j 个元素相同if (nums1[i - 1] == nums2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前元素不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[nums1.size()][nums2.size()]，即 nums1 和 nums2 的 LCS 长度// 这也是不相交的直线段的最大数量return dp[nums1.size()][nums2.size()];}

算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)。

最大子序和

53. 最大子数组和 - 力扣（LeetCode）

之前用过贪心算法解这道题，当子序和为负，则抛弃当前子序和，从下一个位置开始计算子序和。这里使用动态规划也是类似的。

由于是连续的子序和，dp[i]表示到i为止的最大子序和（此处应包含nums[i]）

dp[i] = max(dp[i-1]+nums[i],nums[i])，这里可以想象贪心的思路，当dp[i-1]为负时，自然dp[i-1]+nums[i]要小于nums[i]。

因此，唯一需要的是当前元素的前一位的dp值，dp[0] = nums[0]。

从前往后遍历

最后返回dp数组中的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 创建一个向量 dp，用于存储以第 i 个元素结尾的最大子数组和// 初始化 dp 的大小与 nums 相同，值全部为 0vector<int> dp(nums.size(), 0);// dp[0] 是数组第一个元素的值，因为一个元素的子数组和就是它本身dp[0] = nums[0];// 遍历数组 nums，从第二个元素开始for (int i = 1; i < nums.size(); i++) {// 如果以第 i-1 个元素结尾的最大子数组和小于 0if (dp[i - 1] < 0) {// 则以第 i 个元素结尾的最大子数组和就是第 i 个元素的值// 因为加上前面的子数组和会使得和更小dp[i] = nums[i];} else {// 如果以第 i-1 个元素结尾的最大子数组和大于等于 0// 则将第 i 个元素的值加到以第 i-1 个元素结尾的最大子数组和上// 这样可以保持子数组的连续性dp[i] = dp[i - 1] + nums[i];}}// 使用 STL 中的 max_element 函数找出 dp 中的最大值// 这个最大值就是整个数组的最大子数组和return *max_element(dp.begin(), dp.end());}
};

算法的时间复杂度为O(n),空间复杂度为O(n)。

判断子序列

392. 判断子序列 - 力扣（LeetCode）

同样和最长公共子序列相似，在遍历过程中，当dp[i][j] == s.size()时，表示s为t的子序列，否则s不是t的子序列，具体代码如下。

class Solution {
public:// 定义一个成员函数，用于判断 s 是否为 t 的子序列bool isSubsequence(string s, string t) {// 如果 s 为空字符串，那么它是任何字符串的子序列if (s.size() == 0) {return true;}// 创建一个二维向量 dp，用于存储动态规划的状态值// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的匹配长度vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));// 双层循环遍历 s 和 tfor (int i = 1; i <= s.size(); i++) {  // i 从 1 开始，直到 s.size()for (int j = 1; j <= t.size(); j++) {  // j 从 1 开始，直到 t.size()// 如果 s 的第 i 个字符和 t 的第 j 个字符相同if (s[i - 1] == t[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;// 如果匹配长度等于 s 的长度，说明 s 是 t 的子序列if (dp[i][j] == s.size()) {return true;}} else {// 如果不相同，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这表示当前字符不包含在子序列中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 如果遍历完 dp 数组后没有找到匹配长度等于 s 长度的状态，则 s 不是 t 的子序列return false;}
};

算法的时间复杂度为O(m*n)，空间复杂度为O(m*n)。