代码随想录算法训练营第五十三天|1143.最长公共子序列 1035.不相交的线 53. 最大子序和动态规划

本文主要是介绍代码随想录算法训练营第五十三天|1143.最长公共子序列 1035.不相交的线 53. 最大子序和动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1143.最长公共子序列

体会一下本题和 718. 最长重复子数组的区别
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
题目大意：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 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]);}}}return dp[text1.size()][text2.size()];}
};

时间复杂度: O(n * m)，其中 n 和 m 分别为 text1 和 text2 的长度
空间复杂度: O(n * m)

1035.不相交的线

其实本题和 1143.最长公共子序列是一模一样的，大家尝试自己做一做。
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
题目大意：我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

class Solution {
public:int maxUncrossedLines(vector<int>& A, vector<int>& B) {vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));for (int i = 1; i <= A.size(); i++) {for (int j = 1; j <= B.size(); j++) {if (A[i - 1] == B[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[A.size()][B.size()];}
};

时间复杂度: O(n * m)
空间复杂度: O(n * m)

53. 最大子序和

这道题我们用贪心做过，这次再用dp来做一遍
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
题目大意：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution {
public:int maxSubArray(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> dp(nums.size());dp[0] = nums[0];int result = dp[0];for (int i = 1; i < nums.size(); i++) {dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值}return result;}
};