动态规划


线性DP

  • 经典单串
  • 经典双串

300.最长上升子序列

给定一个无序的整数数组,找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

# 方法一:DP---O(n^2)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        dp=[]
        for i in range(len(nums)):
            dp.append(1)
            dp[i]=max([dp[i]]+[dp[j]+1 for j in range(i) if nums[i]>nums[j]])
        return max(dp)
# 方法二:贪心+二分查找---O(nlogn)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d=[]
        for num in nums:
            if not d or num>d[-1]: d.append(num)
            else:
                l,r=0,len(d)-1
                loc=r
                while l<=r:
                    mid=(l+r)//2
                    if d[mid]>=num:
                        loc=mid
                        r=mid-1
                    else: l=mid+1
                d[loc]=num
        return len(d)

#在nums的遍历中
#1.如果num比末尾大,则直接加入到数组d末尾。
#2.否则,在数组d中二分查找,找到第一个比num小的数d[k],并更新 d[k + 1]=min(d[k+1],num)=num。

1143.最长公共子序列

给定两个字符串 text1text2,返回这两个字符串的最长公共子序列的长度。

输入text1 = "abcde", text2 = "ace"
输出3
解释:最长公共子序列是 "ace",它的长度为 3

#方法一:DP
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        dp=[[0 for j in range(n+1)] for i in range(m+1)]
        #防止dp[i-1]下标超出范围
        for i in range(1,1+m):
            for j in range(1,1+n):
                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])
        return dp[-1][-1]

#经典双串
#一些看起来变态的题,给些提示居然可以写出来。。。
#方法二:
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if text1 == text2:
            return len(text1)
        #if not set(text1).intersection(text2):
           # return 0

        d = collections.defaultdict(list)
        m, n = len(text1), len(text2)
        for i in range(n-1, -1, -1):
            d[text2[i]].append(i)

        nums = []
        for c in text1:
            if c in d:
                nums.extend(d[c])

        ans = []
        for num in nums:
            idx = bisect.bisect_left(ans, num)
            if idx == len(ans):
                ans.append(num)
            else:
                ans[idx] = num
        return len(ans)

53.最大子序和

给定一个整数数组nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

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

152.乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if nums==[]: return 0
        res=float('-inf')
        minn,maxn=1,1
        for n in nums:
            a=n*minn
            b=n*maxn
            maxn=max(n,a,b)
            minn=min(n,a,b)
            if maxn>res:
                res=maxn
        return res

198.打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

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

小结

DP方程:dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])

213.打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

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

树形DP

337.打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连(即父与子关系)的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

class Solution:
    def rob(self, root: TreeNode) -> int:
        return self.helper(root)[1]

    def helper(self, root):
        if not root: return [0,0]
        lv=self.helper(root.left)
        rv=self.helper(root.right)
        return [lv[1] + rv[1], max(lv[1] + rv[1], root.val + lv[0] + rv[0])]

#树形DP,从树的左下构成一个表。
#helper函数返回列表[不含此节点最大值,含此节点最大值]
#经典

other

LCP 19. 秋叶收藏集

小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 ry, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。

出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

#方法一:dp
#    dp[i][0]表示全部为红需要修改几次
#    dp[i][1]表示【红黄】需要修改几次
#    dp[i][2]表示【红黄红】需要修改几次

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n=len(leaves)
        dp=[[0  for i in range(3)] for i in range(n)]
        dp[0][0]= 0 if leaves[0]=='r' else 1
        #print(dp)
        for i in range(1,n):
            dp[i][0]=dp[i-1][0]+(0 if leaves[i]=='r' else 1)
            dp[i][1]=dp[i-1][0]+(0 if leaves[i]=='y' else 1)
            if i>1:
                dp[i][1]=min(dp[i][1],dp[i-1][1]+(0 if leaves[i]=='y' else 1))
                dp[i][2]=dp[i-1][1]+(0 if leaves[i]=='r' else 1)
            if i>2:
                dp[i][2]=min(dp[i][2],dp[i-1][2]+(0 if leaves[i]=='r' else 1))
        #for i in dp: print(i)
        return dp[n-1][2]

# dp表时用[0]*3建表会出错

664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求:

  • 打印机每次只能打印由 同一个字符 组成的序列。
  • 每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。
    给你一个字符串 s ,你的任务是计算这个打印机打印它需要的最少打印次数。
class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[n]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            dp[i][i] = 1
            for j in range(i+1,n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = min([dp[i][k]+dp[k+1][j] for k in range(i,j)])
        return dp[0][n-1]

### dp 666

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录