代码随想录算法训练营第五十三天|1143. 最长公共子序列、1035.不相交的线、53.最大子数组和
LeetCode 1143. 最长公共子序列
题目链接：1143. 最长公共子序列 - 力扣（LeetCode）
和上一题很像，注意状态转移，相同则+1，否则由前面的最大值转移而来。
代码：
#python
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):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]# m,n=len(text1),len(text2)# @cache# def dfs(i,j):# if i<0 or j<0:# return 0# if text1[i]==text2[j]:# return dfs(i-1,j-1)+1# return max(dfs(i-1,j),dfs(i,j-1))# return dfs(m-1,n-1)LeetCode 1035. 不相交的线
题目链接：1035. 不相交的线 - 力扣（LeetCode）
看起来不一样，实际上多读读题，其实就是同一道题啊。
代码：
#python
class Solution:def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:m, n = len(nums1), len(nums2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if nums1[i- 1] == nums2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]LeetCode 53.最大子数组和
题目链接：53. 最大子数组和 - 力扣（LeetCode）
要么加上去，要么重新开始，很简单的DP。
代码：
#python
class Solution:def maxSubArray(self, nums: List[int]) -> int:n = len(nums)dp = [0 for _ in range(n)]dp[0] = nums[0]for i in range(1, n):dp[i] = max(nums[i], dp[i - 1] + nums[i]) //要么是重新开始（因为前面的加起来是负数），要么就前面正数和加当前的值。return max(dp) //注意返回一个最大值