小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

leetcode动态规划

作者：小丑西瓜9 | 2024-04-10 10:50:47

踩

leetcode动态规划

最低票价
最长回文子串
最大子序和
不同路径 II
最小路径和
最大矩形
不同的二叉搜索树 II
不同的二叉搜索树
三角形最小路径和
乘积最大子序列
最大正方形
最长上升子序列
零钱兑换
打家劫舍 II
分割等和子集
最后一块石头的重量 II
完全平方数

暴力递归

暴力递归就是尝试:

把问题转化为规模缩小的同类问题的子问题
有明确的不需要继续进行递归的条件(base case)
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解

递归中出现重复计算时,为了快捷需要将算过的值保存到缓存表里

动态规划模型:
● 从左向右尝试模型
● 范围尝试模型: [ L, R ]: 范围尝试模型特别讨论开头、结尾情况如何如何
● 样本对应模型: 一个样本做行,一个样本做列的样本对应模型

在这里插入图片描述

def ways(N,M,K,P):
  return process(M,K,P,N)

# 递归函数: 
	#	cur: 表示机器人当前的位置, rest: 表示还剩余几步可以走, p为目标位置,N为位置总数
  # 这里的状态变量就是: cur 和rest
def process(cur,rest,P,M):
  # basecase: rest=0 表示机器人已经走完所有的步数
  if rest==0:
    return 1 if cur == P else 0
  # 如果rest> 0 表示还有步数要走
  if cur==1:
    return process(2,rest-1,P,M)
  elif cur ==N:
    return process(N-1,rest-1,P,M)
  else:
    return process(cur-1,rest-1,P,M) + process(cur+1,rest-1,P,M)
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

根据可变参数递归调用过程: 状态转移,发现重复调用值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
假设从7走10步要到达13

在这里插入图片描述
优化1: 记忆化搜索,从顶向下的动态规划

def ways2(N,M,K,P):
  # 使用缓存表: dp[cur][rest]==-1 表示递归没算过,缓存表中不存在
  dp = [[-1 for _ in range(N+1)] for _ in range(K+1)]
  return process2(M,K,P,N)

# 状态变量的变化范围:
cur: 0~N
rest: 0~K

def process2(cur,rest,P,M,dp):
  # 判断是否计算过该状态
  if dp[cur][rest]!=-1 : 
    return dp[cur][rest]
  
  # 没有算过,就去算返回值,并将返回值赛进缓存里
  ans = 0  # 该位置的值,需要更新缓存表的状态
  
  if rest==0:
    ans = 1 if cur == P else 0
  if cur==1:
    ans = process2(2,rest-1,P,M,dp)
  elif cur ==N:
    ans = process2(N-1,rest-1,P,M,dp)
  else:
    ans = process2(cur-1,rest-1,P,M,dp) + process2(cur+1,rest-1,P,M,dp)
  dp[cur][rest] = ans 
  return ans 
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优化2:
从左到右更新状态表:
对于缓存表: 先看basecase 填写缓存表
返回值: 暴力递归函数的主函数的参数值
普遍位置的依赖问题分析:

def ways3(N,M,K,P):
  # 使用缓存表: dp[cur][rest]==-1 表示递归没算过,缓存表中不存在
  dp = [[0 for _ in range(N+1)] for _ in range(K+1)]
  
  dp[P][0] =1     # basecase 更新缓存表
  
  for rest in range(1,K+1): # 从左往右
    dp[1][rest] = dp[2][rest-1]
    
    for cur in range(2,N):  # 从上往下更新缓存表
      dp[cur][rest]= dp[cur-1][rest-1] + dp[cur+1][rest-1]
      
   	dp[N][rest] = dp[N-1][rest-1]
      
  return dp[M][K]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这里插入图片描述

def winer(arr):
  n = len(arr)
  return max(f(0,n-1,arr), g(0,n-1,arr))

# 先手获得最好分数返回
def f(l,r, arr):              ===> f两个状态变量
  # basecase情况 l==r
  if l== r:
    return arr[l]
  return max(arr[l]+g(l+1,r,arr),arr[r]+g(l,r-1,arr))
  
def g(l,r,arr):               ===> g两个状态变量
  # basecase情况 l==r
  if l== r:
    return 0
  return min(f(l+1,r,arr), f(l,r-1,arr)) # 对手拿走某张纸牌,剩余的纸牌中为先手
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这里插入图片描述优化1:

def winer1(arr):
  n = len(arr)
  fdp = [[-1 for _ in range(n)] for _ in range(n)] # 先手函数的缓存表
  gdp = [[-1 for _ in range(n)] for _ in range(n)] # 后手函数的缓存表
 
  return max(f(0,n-1,arr), g(0,n-1,arr))

# 先手获得最好分数返回
def f(l,r, arr):              ===> f两个状态变量
  if fdp[l][r] !=-1:          # 如果计算过这个过程,则直接读,否则计算fdp的状态值
    return fdp[l][r]
  # basecase情况 l==r
  ans =0 
  if l== r:
    ans= arr[l]
  else:
    ans= max(arr[l]+g(l+1,r,arr),arr[r]+g(l,r-1,arr)) 

  fdp[l][r] = ans 
  return ans 
  
def g(l,r,arr):               ===> g两个状态变量
  if gdp[l][r] !=-1:
    return gdp[l][r]
  ans =0
  # basecase情况 l==r
  if l== r:
    return ans
  ans = min(f(l+1,r,arr), f(l,r-1,arr))
  gdp[l][r] =ans 
  return ans # 对手拿走某张纸牌,剩余的纸牌中为先手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在这里插入图片描述

def winer3(arr):
  n = len(arr)
  fdp = [[0 for _ in range(n)] for _ in range(n)] # 先手函数的缓存表
  gdp = [[0 for _ in range(n)] for _ in range(n)] # 后手函数的缓存表
  
  for i in range(n):
    fdp[i][i] =arr[i]
    
  for i in range(1,n):
    l=0
    r=i
    while r <n:
      fdp[l][r] = max(arr[l]+gdp[l+1][r],arr[r]+gdp[l][r-1])  # 将递归改为从表中拿值
    	gdp[l][r] = min(fdp[l+1][r], fdp[l][r-1])
      l+=1
      r+=1
  
  return max(fdp[0][n-1], gdp[0][n-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

背包问题: 从左到右依次尝试模型

def maxValue(w,v,bag):
	process(0,bag,w,v)
  
# 当从左往右依次考虑是否添加当前index对应的货物,返回不超过背包剩余容量的最大价值
# 当前考虑了index号货物,index....所有的货物可以自由选择,做的选择不能超过背包容量,返回最大价值
def process(index,rest,w,v):
  if rest <0:
    return -1
  if index ==n:
    return 0 
 	
  p1 = process(index+1,rest,w,v) # 第一种情况,不要当前的货
  
  p2 =0 
  next = process(index+1,rest-w[index],w,v)
  if next != -1:
    p2= v[index]+next
    
  return max(p1,p2)
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

动态规划优化:

# 先确定参数变化范围:index 0~ n, rest: 负数 ~ bag

def maxValue(w,v,bag):
  n = len(w)
  dp = [[0 for _  in range(n+1)] for i in range(bag+1)] 
  for index in range(n-1,-1,-1):
    for rest in range(bag+1):
      p1 = dp[index+1][rest]
      if rest-w[index] <0:
        p2 =0
      else:
        p2 = v[index]+ dp[index+1][rest-w[index]]
        
      dp[index][rest] = max(p1,p2)
  
	return dp[0][bag]
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在这里插入图片描述

def number(str):
  return process(str,0)

# 从左向右模型
# str[0: i-1]转化无需过问.str[i:]返回有转化转化方法
def process(str,i):
  if i = len(str):  # basecase 模型的右边界, i走到了最后,没有字符可以转化
    return 1   # 表示之前的转化有效
  # i没到最后,说明有字符
  if str[i]=='0':     # 无法转换
    return 0
  # 可能性:1. i位置元素单转 2. i位置和i+1位置一起转
  ans =process(str,i+1)
  if(i+1 < len(str)) and (str[i]-'0')*10 +(str[i+1]-'0')<27:
    ans += process(str,i+2) 
 	return ans
  
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

动态规划优化:

def number(str):
  dp = [0]* (len(str)+1)
  dp[-1] =1
  
  for i in range(len(str)-1,-1,-1): # 从右往左填充
    if str(i) !='0':
      dp[i] = dp[i+1] 
      if(i+1 < len(str)) and (str[i]-'0')*10 +(str[i+1]-'0')<27:
        dp[i] += dp[i+2] 
 
  return dp[0]

1
2
3
4
5
6
7
8
9
10
11
12

最长公共子序列:

def longestCommonSubSequence(str1,str2):
  # 忽略badcase
  n =len(str1)
  m =len(str2)
  return process(str1,str2,n-1,m-1)

# 功能: str1[:i] 和str2[:j] 上的最长公共子序列长度
def process(str1,str2,i,j):
  # basecase情况:
 	if i==0 and j ==0:
    return 1 if str1[i] == str2[j] else 0
  elif i==0:
    return 1 if str1[i]==str2[j] else process(str1,str2,i,j-1)
  elif j==0:
    return 1 if str1[i]==str2[j] else process(str1,str2,i-1,j)
  else :
    # 可能性1 
    p1 = process(str1,str2,i-1,j)
    # 可能性2 
    p2 = process(str1,str2,i,j-1)
    # 可能性3
    p3 = process(str1,str2,i-1,j-1)+1  if str1[i]== str2[j]  else 0
    return max(p1,p2,p3)
    
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

动态规划:

def longestCommonSubSequence(str1,str2):
  # 忽略badcase
  n =len(str1)
  m =len(str2)
  dp = [[0 for _ in range(n)] for _ in range(m)]
  dp[0][0] = 1 if str1[0] == str2[0] else 0 
  for j in range(1,m):
    dp[0][j] = 1 if str1[0] == str2[0] else dp[0][j-1] 
  for i in range(1,n):
  	dp[i][0] = 1 if str1[0] == str2[0] else dp[i-1][0] 
  for i in range(1,m):
    for j in range(1,n):
      tmp= dp[i-1][j-1]+1  if str1[i]== str2[j]  else 0
      dp[i][j]= max(dp[i-1][j],dp[i][j-1],tmp)
  return dp[n-1][m-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

范围尝试模型: 讨论开头和结尾如何如何
讨论在字符串[L,R]区间上的最长回文子序列

在这里插入图片描述
1> 即不以l开头, 也不以r结尾
2> 以l开头, 也不以r结尾
3> 不以l开头, 以r结尾
4> 以l开头, 以r结尾

def lpsl(s):
  return process(s,0,len(s)-1)

def process(s,l,r):
  if l==r:
    return 1
  if r-l ==1:
    return 2 if s[l]==s[r] else 1
  tmp = 0
  if str[l]==str[r]:
    tmp = process(s,l+1,r-1)+2
  return max(process(s,l+1,r-1), process(s,l,r-1),process(s,l+1,r),tmp)
1
2
3
4
5
6
7
8
9
10
11
12

动态规划

def lpsl(s):
  # 两个可变参数
  n= len(s)
  dp = [[0 for _ in range(n)] for _ in range(n) ]  
  for i in range(n):
    dp[i][i] =1
    dp[i][i+1] = 2 if s[l]==s[r] else 1
  for i in range(1,n):
    for j in range(1,n):
      tmp = 0
  		if str[l]==str[r]:
        tmp = dp[l+1][r-1]+2
  		dp[l][r]= max(dp[l+1][r-1], dp[l][r-1],dp[l+1][r],tmp)
       # 进一步优化
      dp[l][r]= max(dp[l][r-1],dp[l+1][r],tmp) #左下角数据一定小于其上左的
  
  return dp[0][n-1]

  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述
样本对应模型:

def jump(a,b,k):
  process(0,0,a,b,k)

def process(x,y,a,b,rest):
  if x<0 or x>9 or y<0 or y>8:  # 跳出越界,无效
    return 0
  if k ==0:
    if x==a and y==b:
      return 1
    else :
      return 0
  return process(x+2,y+1,rest-1,a,b)+process(x+1,y+2,rest-1,a,b)+
process(x-1,y+2,rest-1,a,b)+process(x-2,y+1,rest-1,a,b)
+process(x-2,y-1,rest-1,a,b)+process(x-1,y-2,rest-1,a,b)
+process(x+1,y-2,rest-1,a,b)+process(x+2,y-1,rest-1,a,b)
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

动态规划:

def jump(a,b,k):
  dp = [[[0 for _ in range(a)] for _ in range(b)] for _ in range(k+1)]
  dp[a][b][0]=1
  for rest in range(1,k+1):
    for x in range(a):
      for y in range(b):
        dp[i][j][k]= dp[x+2][y+1][rest-1]+dp[x+1][y+2][rest-1]+
        dp[x-1][y+2][rest-1]+dp[x-2][y+1][rest-1]
        +dp[x-2][y-1][rest-1]+dp[x-1][y-2][rest-1]
        +dp[x+1][y-2][rest-1]+dp[x+2][y-1][rest-1]
    
  return  dp[0][0][k]

1
2
3
4
5
6
7
8
9
10
11
12
13

983. 最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

解题思路：
将days数组展开为men[366]的数组。
我们定义函数

f(i)=f(i-1) if i not in days
else f(i)=min(f(i-1)+costs[0],f(i-7)+costs[1],f(i-30) +costs[2])

代码如下：

class Solution(object):
    def mincostTickets(self, days, costs):
        """
        :type days: List[int]
        :type costs: List[int]
        :rtype: int
        """
        men=[0]*366
        for i in range(days[0],days[-1]+1):
            if i not in days:
                men[i]=men[i-1]
            else:
                men[i]=min(men[i-1]+costs[0],men[i-7]+costs[1],men[i-30]+costs[2])      #当 1-7，i-30 <0时，数组性质
            
        return men[days[-1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
1
2
3

示例 2：

输入: "cbbd"
输出: "bb"
1
2

解题思路：对任意字符串，如果头尾相同，那么它的最长回文子串一定式去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分最长回文子串的较长的那个。
f(i,j) 表示第i 到第j 个字符的回文子串数.

f(i,i)=1
1

第一种情况：f(i,j)=f(i+1,j-1) +2 当s[i] ==s[j]
第二种情况： f(i,j) =max(f(i+1,j) ,f(i,j-1)) 当 s[i] ! =s[j]

代码如下：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        maxl = 0    #用于储存第一个最大子串的长度，后面的子串筛选自动省略小于等于maxl的子串
        start = 0     #储存第一个最大子串的起始位置。
        for i in range(n):
        	# i-maxl>=1 表示可以考虑:i-maxl-1的位置和i两个位置元素加进去考虑是否回文的情况
            if i - maxl >= 1 and s[i-maxl-1: i+1] == s[i-maxl-1: i+1][::-1]:           #添后加s[i]子字符串头尾相同的情况
                start = i - maxl - 1
                maxl += 2
                continue
            if i - maxl >= 0 and s[i-maxl: i+1] == s[i-maxl: i+1][::-1]:           #头尾不同时的情况
                start = i - maxl
                maxl += 1
        return s[start: start + maxl]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)<1:
            return
        n = len(nums)-1
        ans = []
        def process(i):
            if i==0:
                ans.append(nums[i])
                return nums[i]
            p1 = nums[i]+process(i-1)
            p2 = nums[i]
            ans.append(max(p1,p2))
            return max(p1,p2) 
        process(n)
        return max(ans)
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路：利用动态规划的方法，从索引1开始，当他加上前面的元素后，比较该和与当前元素的大小，哪个大留下哪个。最后取数组中最大的值即为最大子集和。寻找最优子结构

def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        array=[nums[0]]*len(nums)   #开辟额外数组   array[i]表示前i个元素中所有添加array[i]形成的最大子序和
        max_sum=nums[0]
        for i in range(1,len(nums)):
            array[i]= max(array[i-1]+nums[i],nums[i])   #加入元素nums[i]后，当前点产生的最大子序和   
            max_sum=max(max_sum,array[i])          #定位最大值
            
        return max_sum

1
2
3
4
5
6
7
8
9
10
11
12
13

63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

在这里插入图片描述
解题思路：构造全0矩阵
代码如下：

 def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m=len(obstacleGrid)                            #not mat but list
        n=len(obstacleGrid[0])
        matrix=[[0 for _ in range(n)]for _ in range(m)]
        if obstacleGrid[0][0]==1:                     #自底向上求解
            return matrix[-1][-1]
        else:
            matrix[0][0]=1
        for i in range(m):
            for j in range(n): 
                if obstacleGrid[i][j]==1:
                    continue
                if i!=0:
                    matrix[i][j]+=matrix[i-1][j]
                if j!=0:
                    matrix[i][j]+=matrix[i][j-1]
    
        return matrix[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
代码如下：

def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m=len(grid)
        n=len(grid[0])
        matrix=[[0 for _ in range(n)] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    matrix[0][0]=grid[0][0]
                elif j==0:
                    matrix[i][j]=matrix[i-1][j]+grid[i][j]
                elif i==0:
                    matrix[i][j]=matrix[i][j-1]+grid[i][j]
                else:
                    matrix[i][j]=min(matrix[i-1][j]+grid[i][j],matrix[i][j-1]+grid[i][j])
        return matrix[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

85. 最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6
1
2
3
4
5
6
7
8

代码如下：

def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        
        r, c = len(matrix), len(matrix[0])
        height, res = [0]*(c+1), 0
        for row in matrix:
            for i in range(c):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            
            stack = [-1]
            for idx, val in enumerate(height):
                while val < height[stack[-1]]:
                    h = height[stack.pop()]
                    res = max(res, h*(idx - stack[-1] - 1))
                    
                stack.append(idx)
                
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        return self.dfs(1,n)
       
    def dfs(self, b, e):#b,e为开始和结束数字
        if b > e:
            return [None]
        res = [] # 存放所有二叉搜索树的根节点
        # 遍历每个子树的根节点
        for rootVal in range(b, e + 1):  
        	# 以当前节点为根节点，构造所有可能的子树，
            leftTree = self.dfs(b, rootVal - 1) # 返回可能子树的所有根节点
            rightTree = self.dfs(rootVal + 1, e)
            for i in leftTree:
                for j in rightTree:
                    root = TreeNode(rootVal)
                    root.left = i
                    root.right = j
                    res.append(root) # 存放子树根节点
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
1
2
3
4
5
6
7
8
9
10

暴力递归

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1:
            return 1
        res = 0
        
        for j in range(1, n + 1):
            res += self.numTrees(j-1) * self.numTrees(n-j)
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解题代码：

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        mem = [0]*(n+1)
        mem[0], mem[1] = 1, 1
        
        for i in range(2, n + 1):   # 表示以1~i为区间构建二叉树的个数
            for j in range(1, i + 1): # 表示在1~i区间上以整数j为根结点可以构造出的二叉搜索树的个数
                mem[i] += mem[j - 1]*mem[i - j] # m[j-1] 表示j-1个整数可以构造左子二叉树的个数, m[i-j]表示i-j个整数可以构建右二叉搜索树的个数
                
        return mem[-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
1
2
3
4
5
6
7
8
9
10
11

代码如下：

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        for i in range(len(triangle) - 1, 0, -1):
            for j in range(i):
                triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1])
        return triangle[0][0]
1
2
3
4
5
6
7
8
9
10

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
1
2

解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
1
2

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res =[]
        
        def process(nums,i):
            if i==0:
                return 1
            ans = 1
            for j in range(i):
                if nums[i]> nums[j]:
                    ans = max(ans, process(nums,j)+1)
                # 如果nums[i]> nums[j]升序就加1, 当j走到i时也就统计出了0~i上以i结尾的最长递增子序列
            return ans
        for i in range(len(nums)):
            cnt = process(nums,i)
            res.append(cnt)
        print(res)
        return max(res)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        B = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(nums),max(B)) 
1
2
3
4
5
6
7
8
9
10
11

最大正方形

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

示例:

代码如下：

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        h = len(matrix)
        if h==0:return 0
        w = len(matrix[0])
        dp = [[0 for i in range(w)] for i in range(h)]
        
        ans = 0
        for i in range(h):
            for j in range(w):
                if i==0 or j==0:
                    dp[i][j] = int(matrix[i][j])
                else:
                    if matrix[i][j]!='0':
                        dp[i][j] = 1 + min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
                    else:
                        dp[i][j]=0
                ans = max(ans,dp[i][j])
                
        return ans**2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
n log n 二分, 维持一个最长上升序列
示例:

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

dp[i] 的值代表nums以nums[i]结尾的最长上升子序列的长度

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11

二分查找
代码：

class Solution:                                                    
    def lengthOfLIS(self, nums: List[int]) -> int:                 
        def findIdxToReplace(dp, i):  # 找第一个比i大的,经典二分套路            
            l, r = 0, len(dp) - 1                                  
            while l < r:                                           
                mid = (l + r) // 2                                 
                if dp[mid] == i:                                   
                    return mid                                     
                elif dp[mid] < i:                                  
                    l = mid + 1                                    
                else:                                              
                    r = mid                                        
            return l                                               
                                                                   
        dp = [nums[0]]  # 第一个数先放进去, 第二个数开始                         
        for i in range(1, len(nums) - 1):                          
            if nums[i] > dp[-1]:                                   
                dp.append(nums[i])                                 
            else:                                                  
                idx = findIdxToReplace(dp, nums[i])                
                dp[idx] = nums[i]                                  
        # 最后一个数只要看能不能加在最后, 替换掉前面的数也增加不了长度了                         
        return len(dp) if nums[-1] <= dp[-1] else len(dp) + 1      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

输入: coins = [2], amount = 3
输出: -1
1
2

暴力递归

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        def func(rest):
            if rest ==0:
                return 0
            ans = 9999999999
            for coin in coins: 
                if coin <= rest:
                    ans = min(ans, func(rest -coin)+1)

            return ans 

        return  -1  if func(amount) == 9999999999 else func(amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码：

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [float("inf")] * (amount+1)
        dp[0] = 0
        for i in range(1,amount+1):

            for coin in coins:
                if i - coin>= 0:
                    dp[i] = min(dp[i],dp[i-coin]+1)
        
        return dp[-1] if dp[-1]!= float("inf") else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

213. 打家劫舍 II

代码：

class Solution(object):
    def rob(self, nums):
        n = len(nums)
        if n == 0:
          return 0
        if n <= 2:
          return max(nums)
        # 不抢第一个
        dp1 = [0] * n
        dp1[0] = 0
        dp1[1] = nums[1]
        for i in range(2, n):
          dp1[i] = max(dp1[i-1],nums[i] + dp1[i-2])

        # 不抢最后一个
        dp2 = [0] * n
        dp2[0] = nums[0]
        dp2[1] = max(nums[0],nums[1])
        for i in range(2, n-1):
          dp2[i] = max(dp2[i-1],nums[i] + dp2[i-2])
        return max(dp1[n-1],dp2[n-2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

0/1背包问题

416. 分割等和子集

暴力递归

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sm= sum(nums)
        if sm % 2 != 0:
            return False
        target = sm /2
        def dfs (i, rest): 
            if i> len(nums)-1:
                return False
            if rest ==0:
                return True
            for j in range(i,len(nums)-1):
                if nums[j] <=rest:
                   return dfs(j+1,rest -nums[j]) or dfs(j+1,rest )
            return False

        return dfs(0, target)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

动态规划：

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        c=sum(nums)
        if c% 2 !=0:
            return False
        c=c//2
        w=[False]*(c+1)
        w[0]=True
        for num in nums:
            for i in range(c,num-1,-1):
            	# num[i] 有两种操作，选择加这个数和不加这个数
                w[i]=w[i] or w[i-num]  
        return w[c]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1049. 最后一块石头的重量 II

class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        c=sum(stones)
        c=c//2
        dp=[0]*(c+1)
        for stone in stones:
            # 对于前stone个石头，对应大小为j的包，对应能装下的最大质量
            for j in range(c,stone-1,-1):
                # 对于石头stone，大小为j的背包容量可以选择加和不加
                dp[j]=max(dp[j],dp[j-stone]+stone)
                
        return sum(stones) -2*dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

279. 完全平方数

状态定义：dp[i]表示n的完全平方数的最少数量
状态转移：遍历1…i内的平方数j*j，j由1开始递增

dp[i] = min(dp[i],dp[i-j*j]+1)
1

边界情况：dp[i]=i

class Solution:
    def numSquares(self, n: int) -> int:
        dp = list(range(n+1))
        for i in range(1,n+1):
            j = 1
            while i - j*j>=0:
                dp[i] = min(dp[i],dp[i-j*j]+1)
                j += 1
        return dp[-1]

1
2
3
4
5
6
7
8
9
10

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/398253

leetcode动态规划

目录

暴力递归

0/1背包问题