CodeTop整理-动态规划篇

目录

72. 编辑距离

53. 最大子序和

300. 最长上升子序列

1143. 最长公共子序列

5. 最长回文子串

121. 买卖股票的最佳时机

139. 单词拆分

221. 最大正方形

152. 乘积最大子数组

42. 接雨水

64. 最小路径和

70. 爬楼梯

123. 买卖股票的最佳时机 III

85. 最大矩形

322. 零钱兑换

96. 不同的二叉搜索树

673. 最长递增子序列的个数

62. 不同路径

279. 完全平方数

32. 最长有效括号

343. 整数拆分

剑指 Offer 42. 连续子数组的最大和

264. 丑数 II

198. 打家劫舍

523. 连续的子数组和

516. 最长回文子序列

131. 分割回文串

1339. 分裂二叉树的最大乘积

718. 最长重复子数组

剑指 Offer 14- I. 剪绳子

面试题 17.24. 最大子矩阵

1227. 飞机座位分配概率

补充题2. 圆环回原点问题

413. 等差数列划分

887. 鸡蛋掉落

44. 通配符匹配

72. 编辑距离

# 72. 编辑距离
# 给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
# 你可以对一个单词进行如下三种操作：
#
# 插入一个字符
# 删除一个字符
# 替换一个字符
#
# 输入：word1 = "horse", word2 = "ros"
# 输出：3
# 解释：
# horse -> rorse (将 'h' 替换为 'r')
# rorse -> rose (删除 'r')
# rose -> ros (删除 'e')

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)
        n=len(word2)
        dp=[[0]*(n+1) for i in range(m+1)]

        for i in range(1,m+1):
            dp[i][0]=i
        for j in range(1,n+1):
            dp[0][j]=j

        for i in range(1,m+1):
            for j in range(1,n+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])+1
        return dp[-1][-1]

53. 最大子序和

# 53. 最大子数组和
# 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
# 子数组 是数组中的一个连续部分。
# 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
# 输出：6
# 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

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

300. 最长上升子序列

# 300. 最长递增子序列
# 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
# 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
# 输入：nums = [10,9,2,5,3,7,101,18]
# 输出：4
# 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp=[1]*len(nums)
        for i in range(1,len(nums)):
            for k in range(i):
                if nums[k]<nums[i]:
                    dp[i]=max(dp[k]+1,dp[i])

        return max(dp)

1143. 最长公共子序列

# 1143. 最长公共子序列
# 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
# 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
#
# 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
# 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
#
# 输入：text1 = "abcde", text2 = "ace"
# 输出：3
# 解释：最长公共子序列是 "ace" ，它的长度为 3 。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m=len(text1)
        n=len(text2)

        dp=[[0]*(n+1) for i in range(m+1)]

        for i in range(m+1):
            dp[i][0]=0
        for j in range(n+1):
            dp[0][j]=0

        for i in range(1,m+1):
            for j in range(1,n+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])
        return dp[-1][-1]

5. 最长回文子串

# 5. 最长回文子串
# 给你一个字符串 s，找到 s 中最长的回文子串。
#
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def find(l, r):
            while (l >= 0 and r < len(s) and s[l] == s[r]):
                l -= 1
                r += 1
            return l, r

        ans = ''
        for i in range(len(s)):
            l1, r1 = find(i, i)
            l, r = l1, r1
            if i > 0:
                l2, r2 = find(i - 1, i)
                if (r2 - l2 > r1 - l1):
                    l, r = l2, r2
            if (len(ans) < r - l - 1):
                ans = s[l + 1:r]
        return ans

121. 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[0]*len(prices)
        min_i=0
        for i in range(1,len(prices)):
            if(prices[min_i]>prices[i]):
                min_i=i
            if(min_i!=i):
                dp[i]=prices[i]-prices[min_i]
        return max(dp)

139. 单词拆分

# 139. 单词拆分
# 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
# 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
# 输入: s = "leetcode", wordDict = ["leet", "code"]
# 输出: true
# 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

from typing import List
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        h=set(wordDict)
        dp=[False]*(len(s)+1)
        dp[0]=True
        for i in range(len(s)+1):
            print(s[:i],h,s[:i] in h)
            if(s[:i] in h):
                dp[i]=True

        for i in range(len(s)+1):
            for j in range(i):
                flag=(s[j:i] in h)
                # print(j,i,dp[j],dp[i],s[j:i],flag)
                if flag and not dp[i]:
                    dp[i]=dp[j] and flag
        return dp[len(s)]

s=Solution()
# s1="leetcode"
# a=["leet","code"]
s1="aaaaaaa"
a=["aaaa","aaa"]
r=s.wordBreak(s1,a)
print(r)

221. 最大正方形

# 221. 最大正方形
# 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

from typing import List
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix)==0 or len(matrix[0])==0:
            return 0
        dp=[[0]*len(matrix[0]) for i in range(len(matrix))]
        maxside=0

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(matrix[i][j]=='1'):
                    dp[i][j]=1
                else:
                    dp[i][j]=0
                maxside=max(maxside,dp[i][j])

        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j]=='1':
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                    maxside=max(maxside,dp[i][j])
        return maxside*maxside
s=Solution()
mat=[["0","1"],["1","0"]]
# mat=[["0"]]
r=s.maximalSquare(mat)
print(r)

152. 乘积最大子数组

# 152. 乘积最大子数组
# 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
# 测试用例的答案是一个32-位 整数。
#
# 子数组 是数组的连续子序列。
# 输入: nums = [2,3,-2,4]
# 输出: 6
# 解释: 子数组 [2,3] 有最大乘积 6。

class Solution:
    # def maxProduct(self, nums: List[int]) -> int:
    def maxProduct(self, nums) :
        dp_min=[0]*len(nums)
        dp_max=[0]*len(nums)
        dp_max[0]=dp_min[0]=nums[0]
        for i in range(1,len(nums)):
            dp_min[i]=min(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i],nums[i])
            dp_max[i] = max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i], nums[i])
        return max(dp_max)

# class Solution:
#     def maxProduct(self, nums: List[int]) -> int:
#         if not nums:
#             return 0
#         max_pro,min_pro,min_cur,max_cur=nums[0],nums[0],nums[0],nums[0]
#         for i in range(1,len(nums)):
#             min_cur,max_cur=min(min(nums[i],min_cur*nums[i]),max_cur*nums[i]),max(min_cur*nums[i],max(max_cur*nums[i],nums[i]))
#             if(max_pro<max_cur):
#                 max_pro=max_cur
#             if(min_pro>min_cur):
#                 min_pro=min_cur
#         print("min_pro:",min_pro)
#         print("max_pro:",max_pro)
#         return max_pro

s=Solution()
# nums=[2,3,-2,4]
nums=[-2,3,-4]
r=s.maxProduct(nums)
print(r)

42. 接雨水

# 42. 接雨水
# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
# 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出：6
# 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
class Solution:
    # def trap(self, height: List[int]) -> int:
    def trap(self, height):
        left=[0]*len(height)
        right=[0]*len(height)
        left[0]=height[0]
        right[-1]=height[-1]

        for i in range(1,len(height)):
            left[i]=max(left[i-1],height[i])
        for i in range(len(height)-2,-1,-1):
            right[i]=max(right[i+1],height[i])
        ans=0
        for i in range(len(height)):
            ans+=min(left[i],right[i])-height[i]
        return ans

64. 最小路径和

# 64. 最小路径和
# 给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
# 说明：每次只能向下或者向右移动一步。
# 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
# 输出：7
# 解释：因为路径 1→3→1→1→1 的总和最小。


class Solution:
    # def minPathSum(self, grid: List[List[int]]) -> int:
    def minPathSum(self, grid):
        dp=[[0]*len(grid[0]) for i in range(len(grid))]
        dp[0][0]=grid[0][0]
        for i in range(1,len(grid)):
           dp[i][0]=grid[i][0]+dp[i-1][0]

        for i in range(1,len(grid[0])):
            dp[0][i]=grid[0][i]+dp[0][i-1]

        for i in range(1,len(grid)):
            for j in range(1,len(grid[0])):
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        return dp[-1][-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
s=Solution()
r=s.minPathSum(grid)
print(r)

70. 爬楼梯

# 70. 爬楼梯
# 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
#
# 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
# 输入：n = 2
# 输出：2
# 解释：有两种方法可以爬到楼顶。
# 1. 1 阶 + 1 阶
# 2. 2 阶

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

123. 买卖股票的最佳时机 III

# 123. 买卖股票的最佳时机 III
# 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
# 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
# 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#
# 输入：prices = [3,3,5,0,0,3,1,4]
# 输出：6
# 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
#     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。


class Solution:
    # def maxProfit(self, prices: List[int]) -> int:
    def maxProfit(self, prices):
        left=[0]*len(prices)
        left_min=prices[0]
        right=[0]*len(prices)

        for i in range(1,len(prices)):
            left_min=min(prices[i],left_min)
            left[i]=prices[i]-left_min

        right_max=prices[-1]
        for i in range(len(prices)-2,0,-1):
            right[i]=right_max-prices[i+1]
            right_max = max(prices[i], right_max)
            right[i]=max(right[i],right[i+1])

        ans=max(left)
        # print(prices)
        # print(left)
        # print(right)
        for i in range(len(prices)):
            ans=max(left[i]+right[i],ans)

        return ans

s=Solution()
prices = [3,3,5,0,0,3,1,4]
r=s.maxProfit(prices)
print(r)

85. 最大矩形

class Solution:
    # def maximalRectangle(self, matrix: List[List[str]]) -> int:
    def maximalRectangle(self, matrix):
        m,n=len(matrix),len(matrix[0])
        pillar=[[0]*len(matrix[0]) for i in range(len(matrix))]
        for i in range(m):
            for j in range(n):
                if matrix[i][j]=='1':
                    if i==0:
                        pillar[i][j]=1
                    else:
                        pillar[i][j]=pillar[i-1][j]+1

        res=0
        for i in range(m):
            # 柱形的最大面积求法，84题
            area_i=0
            left,right=[0]*n,[0]*n
            cur_min=[]
            for j in range(n):
                while cur_min and pillar[i][j]<=pillar[i][cur_min[-1]]:
                    cur_min.pop()
                if cur_min:
                    left[j]=cur_min[-1]
                else:
                    left[j]=-1
                cur_min.append(j)

            cur_min=[]
            for j in range(n-1,-1,-1):
                while cur_min and pillar[i][j]<=pillar[i][cur_min[-1]]:
                    cur_min.pop()
                if cur_min:
                    right[j]=cur_min[-1]
                else:
                    right[j]=n
                cur_min.append(j)

            for j in range(n):
                area_i=max(area_i,(right[j]-left[j]-1)*pillar[i][j])
            res=max(res,area_i)

        return res

322. 零钱兑换

# 322. 零钱兑换
# 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
# 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1。
# 你可以认为每种硬币的数量是无限的

# 输入：coins = [1, 2, 5], amount = 11
# 输出：3
# 解释：11 = 5 + 5 + 1

# 输入：coins = [1, 2, 5], amount = 11
# 输出：3
# 解释：11 = 5 + 5 + 1

from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[float('inf')]*(amount+1)
        dp[0]=0
        for i in range(amount+1):
            for j in range(len(coins)):
                if(coins[j]<=i):
                    dp[i]=min(dp[i],dp[i-coins[j]]+1)
        print(dp)
        ans=-1 if dp[-1]==float('inf') else dp[-1]
        return ans

s=Solution()
coins = [1, 2, 5]
amount = 11
# coins =[2147483647]
# amount = 2
r=s.coinChange(coins,amount)
print(r)

96. 不同的二叉搜索树

# 96. 不同的二叉搜索树
# 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
# dp[j] dp[j-1]*dp[i-j]  我们选择数字 j作为根，则根为j的所有二叉搜索树的集合是左子树集合和右子树集合乘积
class Solution:
    def numTrees(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1

        for i in range(2,n+1):
            for j in range(i+1):
                dp[i]+=dp[j-1]*dp[i-j]
        print(dp)
        return dp[n]

n=10
s=Solution()
r=s.numTrees(n)
print(r)

673. 最长递增子序列的个数

# 673. 最长递增子序列的个数
# 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
# 注意 这个数列必须是 严格 递增的。
# 输入: [1,3,5,4,7]
# 输出: 2
# 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
#
# 输入: [2,2,2,2,2]
# 输出: 5
# 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

from typing import List
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        from collections import defaultdict
        dp=[1]*len(nums)
        cnt=[1]*len(nums)
        max_cnt=0
        max_=1
        for i in range(len(nums)):
            for j in range(i):
                if(nums[i]>nums[j]):
                    if dp[i]<dp[j]+1:
                        dp[i]=dp[j]+1
                        cnt[i]=cnt[j]
                    elif dp[i]==dp[j]+1:
                        cnt[i]+=cnt[j]
            if(dp[i]>max_):
                max_=dp[i]
        ans=0
        for i in range(len(nums)):
            if(max_==dp[i]):
                ans+=cnt[i]
        return ans

# a=[1,3,5,4,7]
# a=[2,2,2,2,2]
a=[1,2,4,3,5,4,7,2]
s=Solution()
r=s.findNumberOfLIS(a)
print(r)

62. 不同路径

# 62. 不同路径
# 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
# 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
# 问总共有多少条不同的路径？
# 输入：m = 3, n = 7
# 输出：28

class Solution:
    # def uniquePaths(self, m: int, n: int) -> int:
    def uniquePaths(self, m, n) :
        dp=[[0]*n for i in range(m)]
        for i in range(m):
            dp[i][0]=1
        for j in range(n):
            dp[0][j]=1

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]

        return dp[-1][-1]

m,n=3,7
s=Solution()
r=s.uniquePaths(m,n)
print(r)

279. 完全平方数

# 279. 完全平方数
# 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
# 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
# 输入：n = 12
# 输出：3
# 解释：12 = 4 + 4 + 4

class Solution:
    def numSquares(self, n: int) -> int:
        import math
        dp=[float('inf')]*(n+1)
        dp[0]=0
        dp[1]=1
        for i in range(2,n+1):
            for j in range(1,int(math.sqrt(n))+1):
                if(j*j<=i):
                    dp[i]=min(dp[i],dp[i-j*j]+1)
        print(dp)
        return dp[-1]

s=Solution()
n = 12
r=s.numSquares(n)
print(r)

32. 最长有效括号

# 32. 最长有效括号
# 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
# 输入：s = "(()"
# 输出：2
# 解释：最长有效括号子串是 "()"

# 动归
# class Solution:
#     def longestValidParentheses(self, s: str) -> int:
#         n=len(s)
#         if n<=0:
#             return 0
#         dp=[0]*(n+1)
#         for i in range(2,n+1):
#             if (s[i-1]==')'):
#                 print(i,i-1,i-2,i-1-dp[i-1]-1)
#                 if(s[i-2]=='('):
#                     dp[i]=max(dp[i],dp[i-2]+2)
#                 if(i-1-dp[i-1]-1>=0 and s[i-1-dp[i-1]-1]=='('):
#                     dp[i]=max(dp[i],dp[i-1]+dp[i-1-dp[i-1]-1]+2)
#         print(dp)
#         return max(dp)

#left ,right
# 动归
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n=len(s)
        if n<=0:
            return 0
        ans =0
        l,r,i=0,0,0
        while(i<n):
            if(s[i]=='('):
                l+=1
            else:
                r+=1
            if(l==r):
                ans=max(ans,2*l)
            elif(r>l):
                l,r=0,0
            i+=1
        l,r,i=0,0,n-1
        while(i>=0):
            if (s[i] == '('):
                l += 1
            else:
                r += 1
            if (l == r):
                ans = max(ans, 2 * l)
            elif (l > r):
                l, r = 0, 0
            i-=1
        return ans

# s1="(()"
# s1="()()"
# s1="()(())"
s1="(()))())("
s=Solution()
r=s.longestValidParentheses(s1)
print(r)

343. 整数拆分

# 343. 整数拆分
# 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
# 返回 你可以获得的最大乘积 。
# 输入: n = 2
# 输出: 1
# 解释: 2 = 1 + 1, 1 × 1 = 1。
# 输入: n = 10
# 输出: 36
# 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
# 将 i 拆分成 i和i−j 的和，且
# i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
# i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]


class Solution:
    def integerBreak(self, n: int) -> int:
        dp=[1]*(n+1)
        dp[0]=0
        dp[2]=1
        for i in range(3,n+1):
            for j in range(1,i):
                dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

        print(dp)
        return dp[-1]
s=Solution()
n=10
r=s.integerBreak(n)
print(r)

剑指 Offer 42. 连续子数组的最大和

# 剑指 Offer 42. 连续子数组的最大和
# 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
# 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
# 输出: 6
# 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

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

        return max(dp)

264. 丑数 II

# 264. 丑数 II
# 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
# 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
# 输入：n = 10
# 输出：12
# 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        cnt=1
        num=1
        a=set()
        while cnt<n:
            a.add(num*2)
            a.add(num*3)
            a.add(num*5)
            num=min(a)
            a.remove(num)
            cnt+=1
        return num

#官网给的动态规划的解法
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        p2 = p3 = p5 = 1

        for i in range(2, n + 1):
            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(num2, num3, num5)
            if dp[i] == num2:
                p2 += 1
            if dp[i] == num3:
                p3 += 1
            if dp[i] == num5:
                p5 += 1

        return dp[n]

198. 打家劫舍

# 198. 打家劫舍
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
#
# 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
# 输入：[1,2,3,1]
# 输出：4
# 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

from typing import List
class Solution:
    def rob(self, nums: List[int]) -> int:
        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-2]+nums[i],dp[i-1])
        return dp[-1]

s=Solution()
a=[1,2,3,1]
r=s.rob(a)
print(r)

523. 连续的子数组和

# 523. 连续的子数组和
# 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
# 子数组大小 至少为 2 ，且
# 子数组元素总和为 k 的倍数。
# 如果存在，返回 true ；否则，返回 false 。
# 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
# 输入：nums = [23,2,4,6,7], k = 6
# 输出：true
# 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

from typing import List
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        h={}
        presum=0
        h[0]=-1
        for i,num in enumerate(nums):
            presum+=num
            presum=presum%k

            if(presum in h ):    #求和不包含下标为i的数
                j=h[presum]
                if i - j >= 2:
                    return True
            else:
                h[presum]=i
        return False

a=[23,2,4,6,6]
k=7
# a=[1,0]
# k=2
s=Solution()
r=s.checkSubarraySum(a,k)
print(r)

516. 最长回文子序列

# 516. 最长回文子序列
# 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
# 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
#
# 输入：s = "bbbab"
# 输出：4
# 解释：一个可能的最长回文子序列为 "bbbb" 。
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for i  in range(n)]  #dp[i][j]  i<=k<=j的最长子串长度
        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+1][j-1]+2   #加上s[i]、s[j]首尾2个节点

                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])  #丢掉s[i]或s[j]后构成的最长回文串
        return dp[0][n-1]

s1 = "bbbab"
s=Solution()
r=s.longestPalindromeSubseq(s1)
print(r)

131. 分割回文串

# 131. 分割回文串
# 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
# 回文串 是正着读和反着读都一样的字符串。
# 输入：s = "aab"
# 输出：[["a","a","b"],["aa","b"]]
from typing import List
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n=len(s)
        f=[[True]*n for i in range(n)]

        for i in range(n-1,-1,-1):
            for j in range(i,n):
                f[i][j]=f[i+1][j-1] and s[i]==s[j]
        print(f)

        ans=[]
        t=[]
        def dfs(i):
            if i==len(s):
                ans.append(t[::])
            for j in range(i,len(s)):
                if f[i][j]:
                    t.append(s[i:j+1])
                    dfs(j+1)
                    t.pop()
        dfs(0)
        return ans
s=Solution()
s1 = "aab"
r=s.partition(s1)
print(r)

1339. 分裂二叉树的最大乘积

# 1339. 分裂二叉树的最大乘积
# 给你一棵二叉树，它的根为root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
#
# 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
# 输入：root = [1,2,3,4,5,6]
# 输出：110
# 解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        def dfs(r):
            if r is None:
                return 0
            return dfs(r.left)+dfs(r.right)+r.val


        allSum=dfs(root)
        ans = 0

        print("allSum",allSum)


        def dfs2(r):
            nonlocal allSum
            nonlocal ans
            if r is None:
                return 0
            left_val=dfs2(r.left)
            right_val=dfs2(r.right)
            cur_sum=left_val+right_val+r.val
            ans=max((allSum-cur_sum)*cur_sum,ans)
            return cur_sum

        dfs2(root)

        return int(ans%(1e9 + 7))

718. 最长重复子数组

# 动态规划解法；a[i][j]表示nums1与nums2的公共最大公共字串的量
# class Solution:
#     # def findLength(self, nums1: List[int], nums2: List[int]) -> int:
#     def findLength(self, nums1, nums2):
#         m,n=len(nums1),len(nums2)
#         a=[[0]*(n+1) for i in range(m+1)]
#
#         for i in range(m):
#             for j in range(n):
#                 if(nums1[i]==nums2[j]):
#                     a[i+1][j+1]=a[i][j]+1
#                 else:
#                     a[i + 1][j + 1] = 0
#         res=0
#         for i in range(1,m+1):
#             for j in range(1,n+1):
#                 res=max(res,a[i][j])
#         return res


# 滑动窗口
#  我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，
#  A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，我们计算它们相对位置相同的重复子数组即可。
class Solution:
    # def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    def findLength(self, nums1, nums2):
        m,n=len(nums1),len(nums2)
        res=0

        def maxLen(i,j,len):   #i为a的开始；j为b的开始；len为保证两者不溢出的长度
            max_len=0
            cur_len=0
            for k in range(len):
                if(nums1[i+k]==nums2[j+k]):
                    cur_len+=1
                else:
                    cur_len=0
                max_len = max(max_len, cur_len)
            # print(max_len)
            return max_len

        # nums1动对齐
        for i in range(m):
            l=min(n,m-i)
            res = max(res, maxLen(i,0,l))

        # nums2动对齐
        for i in range(n):
            l=min(m,n-i)
            res=max(res,maxLen(0,i,l))
        return res

剑指 Offer 14- I. 剪绳子

# 剑指 Offer 14- I. 剪绳子
# 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
# 每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
# 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
# 输入: 2
# 输出: 1
# 解释: 2 = 1 + 1, 1 × 1 = 1

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<3:
            return n-1
        a,b=n//3,n%3
        if b==0: return pow(3,a)
        if b==1: return pow(3,a-1)*4
        return pow(3,a)*2

# dp[i]长为i的绳，剪成m段的最大乘积
class Solution:
    def cuttingRope(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1
        dp[2]=1
        for i in range(3,n+1):
            for j in range(i):
                dp[i]=max(dp[i],j*(i-j),j*dp[i-j])
        return dp[n]

面试题 17.24. 最大子矩阵

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

输入：
[
   [-1,0],
   [0,-1]
]
输出：[0,1,0,1]

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        vector<int> ans(4);//保存最大子矩阵的左上角和右下角的行列坐标
        int N = matrix.size();
        int M = matrix[0].size();
        vector<int> b(M,0);//记录当前i~j行组成大矩阵的每一列的和，将二维转化为一维
        int sum;//相当于dp[i],dp_i
        int maxsum=INT_MIN;//记录最大值
        int bestr1,bestc1;//暂时记录左上角，相当于begin

        for(int i=0;i<N;i++){     //以i为上边，从上而下扫描
            for(int t=0;t<M;t++ ) b[t]=0;    //每次更换子矩形上边，就要清空b，重新计算每列的和
            for(int j=i;j<N;j++){    //子矩阵的下边，从i到N-1，不断增加子矩阵的高
                //一下就相当于求一次最大子序列和
                sum = 0;//从头开始求dp
                for(int k=0;k<M;k++){
                    b[k]+=matrix[j][k];   
//我们只是不断增加其高，也就是下移矩阵下边，所有这个矩阵每列的和只需要加上新加的哪一行的元素
//因为我们求dp[i]的时候只需要dp[i-1]和nums[i],所有在我们不断更新b数组时就可以求出当前位置的dp_i
                    if(sum>0){
                        sum+=b[k];
                    }
                    else{
                        sum=b[k];
                        bestr1=i;//自立门户，暂时保存其左上角
                        bestc1=k;
                    }
                    if( sum > maxsum){
                        maxsum = sum;
                        ans[0]=bestr1;//更新答案
                        ans[1]=bestc1;
                        ans[2]=j;
                        ans[3]=k;
                    }
                }
            }
        }
        return ans;
    }
};

最大和求开始点和结束点文章来源地址https://www.toymoban.com/news/detail-524561.html

class Solution {
public:
    vector<int> maxSubArray(vector<int>& nums) {
        int maxsum=INT_MIN;
        int dp_i = nums[0];
        vector<int> ans(2);//用来记录答案
        int begin = 0;

        for(int i=1 ; i < nums.size() ; i++ ){
            if( dp_i > 0 ){    //dp[i-1] > 0 时
                dp_i+=nums[i];
            }
            else{              //dp[i-1]<0时
                dp_i=nums[i];
                begin = i;     //当nums[i]自立门户时候，我们记录下子序列的起始位置
            }
            if(dp_i > maxsum){//更新答案
                maxsum = dp_i;
                ans[0] = begin;//记录下起始和终止位置
                ans[1] = i;
            }  
        }
        return ans;
    }
    
};

1227. 飞机座位分配概率

# 1227. 飞机座位分配概率
# 有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
#
# 剩下的乘客将会：
#
# 如果他们自己的座位还空着，就坐到自己的座位上，
#
# 当他们自己的座位被占用时，随机选择其他座位
# 第n位乘客坐在自己的座位上的概率是多少？
# 输入：n = 1
# 输出：1.00000
# 解释：第一个人只会坐在自己的位置上


# 当第 1 位乘客选择第 1 个座位时，第 n 位乘客坐在自己的座位上的概率是1.0。
# 当第 1 位乘客选择第 n 个座位时，第 n 位乘客坐在自己的座位上的概率是 0
# 当第 1 位乘客选择其他座位时，其余 n−1 位乘客中有一位乘客的座位被占用，需要随机选择其他座位，因此问题规模从 n 减小至 n−1。

# 递推求解当n>=2时，f(n)=f(n-1)=0.5
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1 if n==1 else 0.5

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n==1:
            return 1
        if n==2:
            return 0.5
        prob=0.5
        for i in range(3,n+1):
            prob=1.0/i+0+(float(i-2)/i)*prob
        return prob

n=10
s=Solution()
r=s.nthPersonGetsNthSeat(n)
print(r)

补充题2. 圆环回原点问题

# 圆环回原点问题
# 圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
# 输入: 2
# 输出: 2
# 解释：有2种方案。分别是0->1->0和0->9->0
# 如果你之前做过leetcode的70题爬楼梯，则应该比较容易理解：走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
#dp[i][j] 走i步到j点的方案
class Solution:
    def backToOrigin(self,n):
        l=10
        dp=[[0]*l  for i in range(n+1)]
        dp[0][0]=1
        for i in range(1,n+1):
            for j in range(l):
                dp[i][j]=dp[i-1][(j-1)%l]+dp[i-1][(j+1)%l]
        return dp[n][0]

413. 等差数列划分

# 413. 等差数列划分
# 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
# 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
# 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
# 子数组 是数组中的一个连续序列。
#
# 输入：nums = [1,2,3,4]
# 输出：3
# 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

from typing import List
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n=len(nums)
        if n<3:
            return 0

        d=nums[1]-nums[0]
        i=2
        ans=0
        t=0
        while(i<n):
            if(nums[i]-nums[i-1]==d):
                t+=1
            else:
                t=0
                d=nums[i]-nums[i-1]
            i+=1
            ans += t
        return ans

s=Solution()
# nums = [1,2,3,4]
nums = [1,2,3]

r=s.numberOfArithmeticSlices(nums)
print(r)

887. 鸡蛋掉落

# 887. 鸡蛋掉落
# 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
#
# 已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
#
# 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
#
# 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少

# https://leetcode.cn/problems/super-egg-drop/solution/ji-ben-dong-tai-gui-hua-jie-fa-by-labuladong/


# def superEggDrop(self, K: int, N: int) -> int:
#     memo = dict()
#
#     def dp(K, N):
#         if K == 1: return N
#         if N == 0: return 0
#         if (K, N) in memo:
#             return memo[(K, N)]
#
#         # for 1 <= i <= N:
#         #     res = min(res,
#         #             max(
#         #                 dp(K - 1, i - 1),
#         #                 dp(K, N - i)
#         #                 ) + 1
#         #             )
#
#         res = float('INF')
#         # 用二分搜索代替线性搜索
#         lo, hi = 1, N
#         while lo <= hi:
#             mid = (lo + hi) // 2
#             broken = dp(K - 1, mid - 1)  # 碎
#             not_broken = dp(K, N - mid)  # 没碎
#             # res = min(max(碎，没碎) + 1)
#             if broken > not_broken:
#                 hi = mid - 1
#                 res = min(res, broken + 1)
#             else:
#                 lo = mid + 1
#                 res = min(res, not_broken + 1)
#
#         memo[(K, N)] = res
#         return res

#     return dp(K, N)



class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        h={}
        def dp(k,n):
            if k==1:
                return n
            if n==0:
                return 0
            if (k,n) in h:
                return h[(k,n)]

            res=float("inf")
            # 直接遍历
            # for i in range(1,n+1):
            #     res=min(max(dp(k-1,i-1),dp(k,n-i))+1,res)

            # 二分遍历
            l,r=1,n
            while(l<=r):
                m=(l+r)//2
                la=dp(k-1,m-1)
                ra=dp(k,n-m)
                if(la>ra):
                    res=min(la+1,res)
                    r=m-1
                else:
                    res=min(ra+1,res)
                    l=m+1
            h[(k,n)]=res
            return res
        dp(k,n)
        print(h)
        return dp(k,n)


# k = 1
# n = 2

k=2
n=6

# k=3
# n=14
s=Solution()
r=s.superEggDrop(k,n)
print(r)

44. 通配符匹配

# 44. 通配符匹配
# 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
# '?' 可以匹配任何单个字符。
# '*' 可以匹配任意字符串（包括空字符串）。
# 两个字符串完全匹配才算匹配成功。
#
# 说明:
#
# s可能为空，且只包含从a-z的小写字母。
# p可能为空，且只包含从a-z的小写字母，以及字符?和*。
#
# 输入:
# s = "aa"
# p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串。

# class Solution:    #超时
#     def isMatch(self, s: str, p: str) -> bool:
#
#         if len(s) == 0 and len(p) == 0:
#             return True
#         if len(s) == 0 :
#             i=0
#             while(i<len(p)):
#                 if p[i]!='*':
#                     break
#                 i+=1
#             if(i==len(p)):
#                 return True
#             return False
#         if len(p) == 0:
#             return False
#
#         if p[0] == '*':
#             return self.isMatch(s, p[1:]) or self.isMatch(s[1:], p)
#         elif (s[0] == p[0] or p[0] == '?'):
#             return self.isMatch(s[1:], p[1:])
#         else:
#             return False

# class Solution:   #超出时限
#     def isMatch(self, s: str, p: str) -> bool:
#
#         if len(s) == 0 and len(p) == 0:
#             return True
#         if len(p) == 0:
#             return False
#         # 判断是否为全*
#         i = 0
#         while (i < len(p)):
#             if (p[i] != '*'):
#                 break
#             i += 1
#         print(s, p,i)
#         if (i == len(p)):
#             return True
#
#         if len(s) == 0:
#             return False
#
#         if i > 0 and p[i - 1] == '*':
#             return self.isMatch(s[1:], p[i - 1:]) or self.isMatch(s, p[i:])
#         if (s[0] == p[0] or p[0] == '?'):
#             return self.isMatch(s[1:], p[1:])
#         return False


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        f=[[False]*(len(p)+1) for i in range(len(s)+1)]
        f[0][0]=True
        for j in range(1,len(p)+1):
            if p[j-1]!='*':
                break
            f[0][j]=True

        for i in range(1,len(s)+1):
            for j in range(1,len(p)+1):
                if  s[i-1]==p[j-1] or p[j-1]=='?':
                    f[i][j]=f[i-1][j-1]
                elif p[j-1]=='*':
                    f[i][j]=f[i][j-1] or f[i-1][j]

        return f[-1][-1]


s=Solution()
s1="adceb"
p="*a*b"
r=s.isMatch(s1,p)
print(r)

到了这里，关于CodeTop整理-动态规划篇的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！