python leetcode Task2 动态规划

leetcode 674:最长连续递增序列

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

leetcode 5:最长回文子串

class Solution:def longestPalindrome(self, s: str) -> str:l=len(s)if l<2:return sdp=[[False for _ in range(l)]for _ in range(l)]max_len=1start=0for j in range(1,l):for i in range(l):if s[i]==s[j]:if j-i<3:dp[i][j]=Trueelse:dp[i][j]=dp[i+1][j-1]if dp[i][j]:cur_len=j-i+1if cur_len>max_len:max_len=cur_lenstart=ireturn s[start:start+max_len]

leetcode 516:最长回文子序列

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

leetcode 72:编辑距离

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

leetcode 198:打家劫舍

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

leetcode 213:打家劫舍II

class Solution:def rob(self, nums: List[int]) -> int:if(not nums):return 0elif len(nums)<=2:return max(nums)def helper(nums):if len(nums)<=2:return max(nums)dp=[0]*len(nums)dp[0]=nums[0]dp[1]=max(nums[0],nums[1])for i in range(2,len(nums)):dp[i]=max(dp[i-1],dp[i-2]+nums[i])return dp[-1]return max(helper(nums[1:]),helper(nums[:-1]))