代码随想录算法训练营第五十天| LeetCode1035.不相交的线、53. 最大子序和、392.判断子序列、115.不同的子序列

1035.不相交的线

题目描述: 1035.不相交的线.

解法

二维dp

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

因为要找不相交的所有相等线,而且连线的顺序绝对遵守原顺序,所以其实就是找最长相等子序列。

滚动dp

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):
        dp = [0] * (len(nums1)+1)
        for i in range(1,len(nums2)+1):
            pre = 0
            for j in range(1,len(nums1)+1):
                cur = dp[j]
                if nums1[j-1] == nums2[i-1]:
                    dp[j] = pre + 1
                else:
                    dp[j] = max(dp[j],dp[j-1])
                pre = cur
        return dp[len(nums1)]

53. 最大子序和

题目描述: 53. 最大子序和.

解法

dp

class Solution(object):
    def maxSubArray(self, nums):
        dp = [0] * len(nums)
        dp[0] = nums[0]
        res = nums[0]
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-1]+nums[i],nums[i])
            res = max(dp[i],res)
        return res

392.判断子序列

题目描述: 392.判断子序列.

解法

二维dp

class Solution(object):
    def isSubsequence(self, s, t):
        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 s[j-1] == t[i-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[len(t)][len(s)] == len(s)

开始编辑距离了

滚动dp

class Solution(object):
    def isSubsequence(self, s, t):
        dp = [0]*(len(s)+1)
        for i in range(1,len(t)+1):
            for j in range(len(s),0,-1):
                if t[i-1] == s[j-1]:
                    dp[j] = dp[j-1] + 1
                else:
                    dp[j] = dp[j]
        return dp[len(s)] == len(s)

如果是由上或者左上决定的,那么就可以用滚动数组,遍历倒叙。如果是由左决定的,使用滚动数组时要正序并且进行记录

115.不同的子序列

题目描述: 115.不同的子序列.

解法

二维dp

class Solution(object):
    def numDistinct(self, s, t):
        # 在s中找t
        # i是t,j是s
        dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
        for i in range(len(s)+1):
            dp[0][i] = 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] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[-1][-1]

一定要注意初始化,此外状态转移也要思考好,i和j的顺序其实无所谓。文章来源地址:https://www.uudwc.com/A/0k4p4/

原文地址:https://blog.csdn.net/WindyAikos/article/details/132881525

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇2023年09月15日 03:49
下一篇 2023年09月15日 03:49