子序列问题

子序列问题

目录

一.单序列问题

1.300. 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

2.674. 最长连续递增序列 - 力扣（LeetCode） (leetcode-cn.com)

 3.53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)

4.647. 回文子串 - 力扣（LeetCode） (leetcode-cn.com)

5.516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)

二.双序列问题

1.718. 最长重复子数组 - 力扣（LeetCode） (leetcode-cn.com)

2.1143. 最长公共子序列 - 力扣（LeetCode） (leetcode-cn.com)

3.1035. 不相交的线 - 力扣（LeetCode） (leetcode-cn.com)

三.编辑距离

1.392. 判断子序列 - 力扣（LeetCode） (leetcode-cn.com)

2.Loading Question... - 力扣（LeetCode） (leetcode-cn.com)

3.583. 两个字符串的删除 *** 作 - 力扣（LeetCode） (leetcode-cn.com)

4.72. 编辑距离 - 力扣（LeetCode） (leetcode-cn.com)

---

---

一.单序列问题 1.300. 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

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

2.674. 最长连续递增序列 - 力扣（LeetCode） (leetcode-cn.com)

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

 3.53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)

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

4.647. 回文子串 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def countSubstrings(self, s: str) -> int:
        if len(s)==1:return 1
        dp=[[False for i in range(len(s))]for j in range(len(s))]
        result =len(s)
        for i in range(len(s)):
            dp[i][i]=True
        for i in range(len(s)):
            for j in range(i):
                if s[i]==s[j] and (i-j<=1 or dp[i-1][j+1]):
                    dp[i][j]=True
                    result+=1
        return result

5.516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)

注意i和j的顺序，否则会有子问题没有处理

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp=[[0 for i in range(len(s))]for j in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        result =1
        for i in range(len(s)):
            for j in range(i-1,-1,-1):
                if s[i]==s[j]:
                    dp[i][j]=2+dp[i-1][j+1]
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j+1])
                result=max(result,dp[i][j])
        return result

二.双序列问题 1.718. 最长重复子数组 - 力扣（LeetCode） (leetcode-cn.com)

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

2.1143. 最长公共子序列 - 力扣（LeetCode） (leetcode-cn.com)

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

3.1035. 不相交的线 - 力扣（LeetCode） (leetcode-cn.com)

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

三.编辑距离

主要就是状态的比较，比如一个母串abfafaa。子串afa

想要得到子串在母串中出现的次数是要分别从两个串的第一个出发，一步步状态转移

比如abfa中af出现的次数，这就是其中一个状态

1.392. 判断子序列 - 力扣（LeetCode） (leetcode-cn.com)

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

2.Loading Question... - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t)==0:return 1
        if len(s)==0:return 0
        dp=[[0 for j in range(len(t)+1)]for i in range(len(s)+1)]
        for i in range(len(s)+1):
            dp[i][0]=1
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+1):
                if s[i-1]==t[j-1]:
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[-1][-1]

3.583. 两个字符串的删除 *** 作 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp=[[0 for i in range(len(word2)+1)] for j in range(len(word1)+1)]
        result=0
        #最长公共子序列
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[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 len(word1)+len(word2)-2*dp[-1][-1]

4.72. 编辑距离 - 力扣（LeetCode） (leetcode-cn.com)

如果当前处理到了i,j，是默认0到i-1 和 0到j-1的 经过n步 *** 作已经达到了相同

如果i和j处相等，那么就等于n

如果i和j处不等，那么肯定要在之前的基础上加1次

那么之前的基础就取决于现在的 *** 作

我们可以直接修改i使其和j相等，那么这种情况就只要在i-1和j-1的基础上加1即可

如果我们是给i插入一个和j相等的，那么这种情况只要看i和j-1的次数加1

如果是给i删除一个和j不相等的，那么就只要看i-1和j的次数加1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if len(word1)==0:return len(word2)
        if len(word2)==0:return len(word1)
        dp=[[0 for i in range(len(word2)+1)]for j in range(len(word1)+1)]
        for i in range(1,len(word2)+1):
            dp[0][i]=i
        for i in range(1,len(word1)+1):
            dp[i][0]=i
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=1+min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
        return dp[-1][-1]