674:最长连续递增序列
链接：674. 最长连续递增序列 - 力扣（LeetCode）
1 class Solution: 2 def findLengthOfLCIS(self, nums: List[int]) -> int: 3 n=len(nums) 4 dp=[1]*n 5 if(n<1): return 0 6 for i in range(1,n): 7 if(nums[i]>nums[i-1]): 8 dp[i]=max(dp[i],dp[i-1]+1) 9 return max(dp)findLengthOfLCIS
718：最长重复子序列
链接：718. 最长重复子数组 - 力扣（LeetCode）
1 class Solution: 2 def findLength(self, nums1: List[int], nums2: List[int]) -> int: 3 #dp[i][j]数组nums1中第i-1号元素之前与数组nums2中第j-1号元素之前的最长重复子数组 4 #dp[i][j]=dp[i-1][j-1]+1 5 m,n=len(nums1),len(nums2) 6 re=0 7 dp=[[0 for i in range(n+1)] for j in range(m+1)] 8 for i in range(1,m+1): 9 for j in range(1,n+1): 10 if(nums1[i-1]==nums2[j-1]): dp[i][j]=dp[i-1][j-1]+1 11 re=max(re,dp[i][j]) 12 return refindLength
1143:最长公共子序列
链接：1143. 最长公共子序列 - 力扣（LeetCode）
1 class Solution: 2 def longestCommonSubsequence(self, text1: str, text2: str) -> int: 3 m,n,=len(text1),len(text2) 4 dp=[[0 for i in range(n+1)] for j in range(m+1)] 5 re=0 6 for i in range(1,m+1): 7 for j in range(1,n+1): 8 if(text1[i-1]==text2[j-1]): dp[i][j]=dp[i-1][j-1]+1 9 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) 10 re=max(re,max(dp[i])) 11 print(dp) 12 return relongestCommonSubsequence
1035:不相交的线
和1143一样
1 class Solution: 2 def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: 3 #dp[] 4 m,n=len(nums1),len(nums2) 5 dp=[[0 for i in range(n+1)] for j in range(m+1)] 6 re=0 7 for i in range(1,m+1): 8 for j in range(1,n+1): 9 if(nums1[i-1]==nums2[j-1]): dp[i][j]=dp[i-1][j-1]+1 10 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) 11 re=max(re,max(dp[i])) 12 return remaxUncrossedLines
53:最大字数和
1 class Solution: 2 def maxSubArray(self, nums: List[int]) -> int: 3 n=len(nums) 4 dp=[0]*n 5 dp[0]=nums[0] 6 for i in range(1,n): 7 dp[i]=max(nums[i],dp[i-1]+nums[i]) 8 #print(dp) 9 return max(dp)maxSubArray
392:判断子序列
1 class Solution: 2 def isSubsequence(self, s: str, t: str) -> bool: 3 n,m=len(s),len(t) 4 re=0 5 dp=[[0 for i in range(m+1)] for j in range(n+1)] 6 for i in range(1,n+1): 7 for j in range(1,m+1): 8 if(s[i-1]==t[j-1]): dp[i][j]=dp[i-1][j-1]+1 9 else: dp[i][j]=dp[i][j-1] 10 re=max(re,max(dp[i])) 11 print(dp) 12 if(re==n): return True 13 return FalseisSubsequence
115:不同的子序列
1 class Solution: 2 def numDistinct(self, s: str, t: str) -> int: 3 #获取指定子序列的方法 4 m,n=len(s),len(t) 5 dp=[[0 for i in range(n+1)]for j in range(m+1)] 6 for i in range(m+1): dp[i][0]=1 7 for i in range(1,m+1): 8 for j in range(1,n+1): 9 if(s[i-1]==t[j-1]): dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 10 else: dp[i][j]=dp[i-1][j] 11 return dp[-1][-1]numDistinct
583:两个字符串的删除操作
链接：583. 两个字符串的删除操作 - 力扣（LeetCode）
1 class Solution: 2 def minDistance(self, word1: str, word2: str) -> int: 3 m,n=len(word1),len(word2) 4 dp=[[0 for i in range(m+1)]for j in range(n+1)] 5 for i in range(n+1): dp[i][0]=i 6 for i in range(m+1): dp[0][i]=i 7 for i in range(1,n+1): 8 for j in range(1,m+1): 9 if(word1[j-1]==word2[i-1]): dp[i][j]=dp[i-1][j-1] 10 else: dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2) 11 return dp[-1][-1]minDistance
72：编辑距离
修改单词有三种方式：增、删、换
word1删i-1元素dp[i-1][j]，word2删j-1元素dp[i][j-1]，word1和word2都删dp[i-1][j-1]+2 替换dp[i-1][j-1]+1，替换后word1[i-1]=word2[j-1] 添加=删除的逆向操作，word1增加一个单吃=word2减去一个单词
1 class Solution: 2 def minDistance(self, word1: str, word2: str) -> int: 3 len1,len2=len(word1),len(word2) 4 dp=[[0 for i in range(len2+1)]for j in range(len1+1)] 5 for i in range(len1+1): dp[i][0]=i 6 for i in range(len2+1): dp[0][i]=i 7 for i in range(1,len1+1): 8 for j in range(1,len2+1): 9 if(word1[i-1]==word2[j-1]): dp[i][j]=dp[i-1][j-1] 10 else: dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1) 11 #word1删i-1元素dp[i-1][j],word2删j-1元素dp[i][j-1],word1和word2都删dp[i-1][j-1]+2 12 #替换dp[i-1][j-1]+1 13 #添加=删除的逆向操作 14 return dp[-1][-1]minDistance
647：回文子串
1 class Solution: 2 def countSubstrings(self, s: str) -> int: 3 #dp[i][j] i到j范围内串是否是回文 4 #s[i]=s[j] j-i<=1,aa，s[i:j]是回文，j-i>1,dp[i+1][j-1]是回文，s[i:j]是回文 5 n,re=len(s),0 6 dp=[[False for i in range(len(s))]for j in range(len(s))] 7 for i in range(len(s)-1,-1,-1): 8 for j in range(i,len(s)): 9 if(s[i]==s[j]): 10 if(j-i<=1): 11 dp[i][j]=True 12 re+=1 13 elif(dp[i+1][j-1]): 14 dp[i][j]=True 15 re+=1 16 return re 17countSubstrings
516:最长回文子序列
链接：516. 最长回文子序列 - 力扣（LeetCode）
1 class Solution: 2 def longestPalindromeSubseq(self, s: str) -> int: 3 #dp初始化，i=j,dp[i][j]=1 4 #遍历顺序：i倒序，j正序 5 n=len(s) 6 dp=[[0 for i in range(n)]for j in range(n)] 7 for i in range(n): dp[i][i]=1 8 for i in range(n-1,-1,-1): 9 for j in range(i+1,n): 10 if(s[i]==s[j]): dp[i][j]=dp[i+1][j-1]+2 11 else: dp[i][j]=max(dp[i+1][j],dp[i][j-1]) 12 return dp[0][-1]longestPalindromeSubseq
标签：re,int,max,len,第十四天,range,Leetcode,dp,刷题 From： https://www.cnblogs.com/xiaoruru/p/18034572