1143.最长公共子序列

体会一下本题和 718. 最长重复子数组 的区别
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.最长公共子序列.html

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

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

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

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

思考

注意这道题的DP定义和前面都不太一样了
确定dp数组（dp table）以及下标的含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？
这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以，我在 动态规划：718. 最长重复子数组 中的「拓展」里 详细讲解了区别所在，其实就是简化了dp数组第一行和第一列的初始化逻辑。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        # dp[i][j] 为以text1[0:i]即i-1结尾 text2[0:j] 即j-1结尾 两个字符串的最长公共子序列长度
        dp = [[0] * (n2+1) for _ in range(n1+1)]
        for i in range(n1):
            for j in range(n2):
                if text1[i] == text2[j]:
                    dp[i+1][j+1]=dp[i][j]+1
                else:
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
        return dp[n1][n2]

1035.不相交的线

其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.不相交的线.html

53. 最大子序和

这道题我们用贪心做过，这次 再用dp来做一遍
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
https://programmercarl.com/0053.最大子序和（动态规划）.html
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 以i为结尾的数组的最大子数组和
        dp = [0] * len(nums)
        dp[0] = nums[0]
        max_sum = nums[0]
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-1] + nums[i] ,nums[i])
            max_sum = max(dp[i],max_sum)
        return max_sum

392.判断子序列

这道题目算是 编辑距离问题 的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的 编辑距离问题了

https://programmercarl.com/0392.判断子序列.html