本文主要是介绍代码随想录算法训练营四十三天|1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：1143. 最长公共子序列 - 力扣（LeetCode）
思路：
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i-1][j] 与 dp[i][j-1]
class Solution(object):def longestCommonSubsequence(self, text1, text2):""":type text1: str:type text2: str:rtype: int"""dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]for i in range(1, len(text2) + 1):for j in range(1, len(text1) + 1):if text1[j-1] == text2[i-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[len(text2)][len(text1)]题目链接：1035. 不相交的线 - 力扣（LeetCode）
思路：跟上题思路一样，都是不相邻找最长共同
class Solution(object):def maxUncrossedLines(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: int"""dp = [[0] * (len(nums1) + 1) for _ in range(len(nums2) + 1)]for i in range(1, len(nums2) + 1):for j in range(1, len(nums1) + 1):if nums1[j-1] == nums2[i-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[len(nums2)][len(nums1)]题目链接：53. 最大子数组和 - 力扣（LeetCode）
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""dp = [-float('inf')] * len(nums)dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1] + nums[i])return max(dp)题目链接：392. 判断子序列 - 力扣（LeetCode）
思路：跟最长公共子序列一样，如果最长公共子序列等于s 那么就是True
class Solution(object):def isSubsequence(self, s, t):""":type s: str:type t: str:rtype: bool"""dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]result = 0for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])result = result if result > dp[i][j] else dp[i][j]return True if result == len(s) else False这篇关于代码随想录算法训练营四十三天|1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
