day45|300最长递增子序列674最长连续递增序列718最长重复子数组1143最长公共子序列1035不相交的线53最大子序和392判断子序列115不同的子序列583两个字符串的删除操作

前言

所有的所谓删除操作，其实就是不考虑这个元素的意思，例如递推公式在中的dp[i][j]变成dp[i-1][j]这样就少考虑了一个元素

300.最长递增子序列

思路

本题直接照抄的，重点是掌握dp的含义，自己想不到；有一种遍历的感觉
dp五部曲：

1. dp的含义：dp【i】表示以nums【i】结尾的最长递增子序列的长度；
2. 递推方程：dp【i】等于0到i-1的各个位置的最长升序子序列+1的最大值，当然同时也满足nums[i] > nums[j]；
   所以递推方程是if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
3. 初始化：dp【i】=1，肯定至少是自己
4. 遍历顺序：
   dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

方法一

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [1 ]* len(nums)
        for i in range(1,len(nums)):
            for j in range(0,i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

方法二 贪心没看

674. 最长连续递增序列

思路

动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义:dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
2. 递推公式：如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
   即：dp[i] = dp[i - 1] + 1;
   

方法一

自己直接写出来，相较于前面一题简单一些，还是一样的dp含义，但是不同点在于不用第二次遍历了，如果是连续的话那么一定是从前面一项起；否则就是自己，长度为1；

class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [1] * len(nums)
        for i in range(1,len(nums)):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
        return max(dp)

方法二

718. 最长重复子数组

思路

经典的动态规划题
🩷🩷🩷🩷🩷🩷🩷注意！！！子数组要求必须是连续的！！！和下面一题1143区分开来
总体思路：两层遍历，dp[i][j] 表示num1以i结尾，nums2以j结尾的时候的子数组长度，那么只要比较当前元素是否相等，如果向相等，就是之前的+1，不相等，🩵🩵就是0；

这里一开始没理解：
五部曲：

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

此时细心的同学应该发现，那dp[0][0]是什么含义呢？总不能是以下标-1为结尾的A数组吧。

其实dp[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从1开始。

那有同学问了，我就定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？

**行倒是行！ 但实现起来就麻烦一点，需要单独处理初始化部分，**在本题解下面的拓展内容里，我给出了 第二种 dp数组的定义方式所对应的代码和讲解，大家比较一下就了解了。
2. 递推公式：即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;据递推公式可以看出，遍历i 和 j 要从1开始！
3. 初始化：在这里卡哥dp[i][0] 和dp[0][j]初始化为0。因为按照他的思路是从1开始的
4.
5.

方法一 自己写的

没有用i-1和j-1的下标
错误点

1. 初始化的时候nums2和nums1写反了
2. 初始化nums2的时候注意从1开始，否则dp[0][0]这个位置算了两遍

class Solution(object):
    def findLength(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        result = 0
        dp = [[0] * len(nums2) for _ in range(len(nums1))]
        for i in range(len(nums1)):
            if nums2[0] == nums1[i]:
                dp[i][0] += 1
                if dp[i][0] > result:
                    result = dp[i][0] 
        for j in range(1,len(nums2)):
            if nums1[0] == nums2[j]:
                dp[0][j] += 1
                if dp[0][j] > result:
                    result = dp[0][j] 
        for i in range(1,len(nums1)):
            for j in range(1,len(nums2)):
                if</