代码随想录算法训练营第52天 | 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

代码随想录系列文章目录

动态规划篇 —— 最长子序列

---

---

300.最长递增子序列

题目链接

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 1: return 1
        dp = [1] * (len(nums))
        res = 1
        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)
            res = max(res, dp[i])
        return res
1
2
3
4
5
6
7
8
9
10

这个题昨天做过一遍，思路总结在上一个打卡里了
但是今天做的时候又有点小bug, 就是 dp[i] = max(dp[i], dp[j]+1)这里。
我写成了dp[i] = dp[j]+1
如果写成这样的话，在遍历到当前这个i位置的时候，i前面的所有位置的结果dp[j]都可以参与当前这个位置值的计算，我们要一直不断的迭代选择大的，如果没有max的话，那就是取最后一个dp[j]+1的值作为dp[i]了

674. 最长连续递增序列

题目链接

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 1: return 1
        dp = [1] * (len(nums))
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]: dp[i] = dp[i-1] + 1 
            else: dp[i] = 1
        return max(dp)
1
2
3
4
5
6
7
8

这个题我在做了上道题之后，头也不回的一次就a出来了
因为我明白了这个连续，dp[i]只能从dp[i-1]推导过来，如果dp[i] > dp[i-1]的话，dp[i]更新
不然的话，那个位置的值就是保持1

718.最长重复子数组

题目链接
1.状态定义

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。

2.状态转移

注意这题仍然是子数组也就是子序列，所以只有nums[i-1] == nums[j-1]的时候，当前的dp[i][j]才能转移过来 即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;

根据递推公式可以看出，遍历i 和 j 要从1开始！

3.base case

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！

但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化为0。

举个例子A[0]如果和B[0]相同的话，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，正好符合递推公式逐步累加起来。

其它位置都初始化为0

4.遍历顺序以及解的位置

正序遍历就好了

解的位置的话需要在遍历的时候记录一下，这个res要初始化为0，因为例子中的情况是0

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
        res = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                if nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
                res = max(res, dp[i][j])
        return res
1
2
3
4
5
6
7
8
9

这个题也不难