代码随想录算法训练营第四十四天|leetcode1143.最长公共子序列、leetcode1035.不相交的线、leetcode53. 最大子序和、leetcode392.判断子序列

1 leetcode1143.最长公共子序列

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划子序列问题经典题目 | LeetCode：1143.最长公共子序列哔哩哔哩bilibili

思路：其实我比较清楚的是和上面一道题目的思路，差不太多，但是我不知道非连续的位置应该如何赋值，然后就容易搞错

1.1视频后的方法

主要就是递推公式，不知道那一块如何进行往后写，但是不知道0的位置应该怎么办但是能理解一点了吧

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
        result = 0
        for i in range(1,len(text1)+1):
            for j in range(1,len(text2)+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[-1][-1]

1.2 本题小结

1. 主要就是动态规划里面的一个循环，是从哪儿开始的，条件判断处的值

2. 然后就是我在写的时候，就是会不知道这一块，前面的数值，应该如何往后计算，希望越来越熟悉一点吧，慢慢来

2 leetcode1035.不相交的线

题目链接：1035. 不相交的线 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划之子序列问题，换汤不换药 | LeetCode：1035.不相交的线哔哩哔哩bilibili

思路：其实就是上一道题目的变体，换了一种说法而已，才开始被迷惑住了，以为是从后往前便利的顺序，结果写出来只能满足一小部分的要求

2.1 自己的方法

真的，代码都没啥区别，只是换了一种说法，感觉就是

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
        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
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]

2.2 本题小结

1. 思路代码等都是差不多的，没区别，还是要自己多去看多去思考呀

2. 甚至遍历顺序啥的都没有任何的变化，嗯，希望自己继续加油吧

3 leetcode53. 最大子序和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：看起来复杂，其实是简单动态规划 | LeetCode：53.最大子序和哔哩哔哩bilibili

思路：就是递推公式的变化吧，开始就猜到了应该是这里的问题了

3.1 视频后的思路

哈哈哈哈哈哈，遇到了一个新的Bug，那就是初始化结果，初始化错误了

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        dp = [0]*len(nums)
        dp[0] = nums[0]
        result = dp[0]
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-1]+nums[i],nums[i])
            result = max(result,dp[i])
        return result

3.2 本题小结

1. 嗯，当时忘记的事情就是在递推公式里面，忘记了比较大小的时候写错了，但是理论上就是这个含义

2. 这一块还是要多想多些吧，真的会自己迷惑住

4 leetcode392.判断子序列

题目链接：392. 判断子序列 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划，用相似思路解决复杂问题 | LeetCode：392.判断子序列哔哩哔哩bilibili

思路：就是跟公共子序列一模一样的思路，只是最后的输出需要变换一下

4.1 自己的方法

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp = [[0]*(len(s)+1) for _ in range(len(t)+1)]
        for i in range(1,len(t)+1):
            for j in range(1,len(s)+1):
                if t[i-1] == s[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[-1][-1] == len(s)

4.2 本题小结

1. 这个题目真的思路和找最长子序列的方法一模一样，就这样慢慢写，感觉就是输出的地方不一样，其他的就是正常的了

2. 终于自己也是可以逐步支棱起来了，但是就是自己写的时候就会迷惑一点吧，希望接下来会好一些

5 今日小结

1. 今天的思路其实都挺简单的，也可能是做了很多类似的题目，所以感觉自己可以继续写下去了

2. 这一块终于也快迎来了结束，继续加油吧