动态规划习题——

1143.最长公共子序列

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
 
        n=len(text1)
        m=len(text2)
 
        dp=[[0]*(m+1) for _ in range(n+1)]
 
        for i in range (1,n+1):
            for j in range(1,m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j]=1 + dp[i-1][j-1]
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        
        return dp[n][m]

120.三角形最小路径和

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp=triangle
        le=len(triangle)
 
        for i in range(le-2,-1,-1):
            for j in range (len(triangle[i])):
                dp[i][j]=dp[i][j]+min(dp[i+1][j],dp[i+1][j+1])
        return dp[0][0]

53.最大子数组和

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

—前戳和解法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 利用前缀和初始化
        n=len(nums)+1
        sum_=[0]*n
        for i in range (1,n):
            sum_[i]=sum_[i-1]+nums[i-1]
        # 子区间最大  =sum[i]-sum[j]
        # 所以要使sum[j]最小
        prev=[0]*n
        for i  in range(1,n):
            # 初始化prev[i]
            prev[i]=min(prev[i-1],sum_[i])
        
        ans=-1e10
        for i in range(1,n):
            ans=max(ans,sum_[i]-prev[i-1])
 
        return ans