2023年8月1日发(作者：)

⼒扣刷题-python-动态规划-1（动态规划、01背包问题、完全背包问题）⽂章⽬录1.动态规划动态规划 是由前⼀个状态推导出贪⼼算法 是直接取局部最优动态规划需要直到状态转移公式解题过程分为5步1. 确定dp数组（dp table）以及下标的含义2. 确定递推公式3. dp数组如何初始化4. 确定遍历顺序5. 举例推导dp数组2.简单和中等题其实也不⽤写dp数组，这道题就可以解出来，但是这道题还是⽤了动态规划的思想，每个数之间是有关系的12345678class Solution: def fib(self, n: int) -> int: if n<2:return n a, b = 0, 1 for i in range(n-1): a=a+b a,b=b,a return b这道题同上⼀道题class Solution: def climbStairs(self, n: int) -> int: #每次爬台阶相当于是 n-1情况

和n-2情况和， dp=[] for i in range(n): if i<2: (i+1) else: dp[0]+=dp[1] dp[0],dp[1]=dp[1],dp[0] return dp[-1]进阶版的爬楼梯class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: #dp[i]为某⼀层花费 dp[i] =min(dp[i-1] dp[i-2])+cost[i] #dp[0]=1 dp[1]=100 dp = [0]*len(cost) #提前配置好空间，再赋值会快很多 for i in range(len(cost)): if i <2: dp[i]=cost[i] else:dp[i]= min(dp[i-1],dp[i-2]) + cost[i] return min(dp[-2:])这道题和爬楼梯类似，不过是⼀个⼆维的class Solution: def uniquePaths(self, m: int, n: int) -> int: #第mn

⾏肯定是

第m-1 n

⾏

和第m n-1⾏移动过来的 #dp表⽰mn位置的条数 dp[m][n] #初始化 m=0位置为1 n=0位置为1

因为边上只有⼀条路径可以⾛ dp= [[1]*n for _ in range(m)] 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]class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: #同前⼀道题，但是加⼊了障碍物，所以要将障碍物位置变为0，

dp = obstacleGrid for i in range(len(dp)): for j in range(len(dp[0])): if not dp[i][j]-1: dp[i][j]=0 elif not i and not j :dp[i][j]=1 else: dp[i][j] =(dp[i-1][j] if i>0 else 0)+(dp[i][j-1] if j >0 else 0) return dp[-1][-1]这道题的确不好想，⽽且 是个⼆维的循环，以后在动态规划，可能会经常⽤到。class Solution: def integerBreak(self, n: int) -> int: #第n个

相当于

第n

分解成 n-i和i乘积

和dpn-i和i乘积⽐较

选最⼤的 #虽然n是从2开始的

相当于只有n-2+1

个

但是为了遍历⽅便扩充成n个 dp= [_+1 for _ in range(n)] for i in range(n): for j in range(1,i): dp[i] = max(dp[i] , max(dp[i-j]*j,(i-j)*j)) #print(dp) return dp[-1] if n>=4 else n-1 1112class Solution: def numTrees(self, n: int) -> int: #dp

为n情况下⼆叉搜索树的个数 #dp[i] +=dp[i-j-1]dp[j] for j in range(i) dp= [0]*(n+1)

for i in range(n+1): if i < 2: dp[i]=1 else: for j in range(i):dp[i] +=dp[i-j-1]*dp[j] #print(dp)

return dp[-1]3.01背包问题基础1.01背包基础背包问题是个啥，我⼀直很好奇，今天终于看到这⾥了，先看下基础理论。171819# -*- coding: gbk -*-#暴⼒解法nmax=3nlist=[15,20,30]nweigt=[1,3,4]res= []def backtracking(n,weight,hw): if not n - nmax :return (hw) for i in [0,1]: if i: #选择

hw+= nlist[n-1] weight-=nweigt[n-1]

backtracking(n+1,weight,hw)

backtracking(1,4,0)print('所有可能的情况为：',res)print('可以放⼊最⼤为：',max(res))暴⼒解法肯定是不可取的，⽤的时间为o（2^n)当这个物体n特别多的时候，这样就太浪费时间了，肯定暴⼒的⽅法是不可取的2.01背包问题的动态规划（⼆维数组）1）定义2）递推关系如果某⼀⾏ 即某⼀个物品i 在j⼩于weight[i]时候，直接取 dp[i-1][j]如果⼤于weight[i]时候，就可以⽐较他放⼊与不放⼊的总重量的⼤⼩，肯定选最⼤的那个dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])3）初始化全部初始化为0，但是每次都是和i-1⽐较，所以要初始化i=0⾏4）遍历顺序选择⼀⾏⼀⾏遍历，就是⼀个物品⼀个物品来5）对⽐dp数组并修改程序1112weight=[1,3,4]value=[15,20,30]n=4dp= [[0]*(n+1) for _ in range(len(weight))]for j in range(n+1): #初始化第⼀⾏ if j>=weight[0]: dp[0][j] = value[0]for i in range(1,len(weight)): for j in range(1,n+1): if j

表⽰j表⽰此时的还剩下的重量 dp表⽰总价值#dp[j] =max(dp[j-weight[i]]+value[i],dp[j])weight=[1,3,4]value=[15,20,30]n=4dp= [0 for _ in range(n+1)]for i in range(len(weight)): for j in range(n,weight[i]-1,-1): #这⾥⽤了从⼤到⼩的顺序，⽽且只取到物品的⼤⼩，前⾯全是原来的

很巧妙 dp[j] =max(dp[j-weight[i]] +value[i],dp[j])print(dp)4.01背包问题这道题就是典型的背包问题class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums)%2: return False target=sum(nums)//2 pd=[0]*(target+1) for i in range(len(nums)): for j in range(target,nums[i]-1,-1): pd[j]=max(pd[j-nums[i]]+nums[i],pd[j]) if not pd[-1]-target :return True else:return False1112class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: #把⽯头分成两堆

让两堆的数量尽量接近

#这就变成01背包问题，就是让选出数量尽量接近平均数 sumer = sum(stones) target = sumer//2 dp = [0]*(target+1) for i in range(len(stones)): for j in range(target, stones[i]-1,-1): dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]) #print(dp,sumer) return sumer-2*dp[-1]111213class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: #dp为填满target⼤⼩的可能情况 suber =(sum(nums)-target) target = suber//2 if suber%2 or target<0 :return 0 dp = [0]*(target+1) dp[0]=1 #装满容量为0的背包，有1种⽅法，就是装0件物品。 for i in range(len(nums)): for j in range(target,nums[i]-1,-1): dp[j] +=dp[j-nums[i]] return dp[-1]111213class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: #dp

为i个0和j个1情况下最⼤⼦集 dp = [[0]*(n+1) for _ in range(m+1)]

for strer in strs: zeroer= ('0') oneser= ('1') for i in range(m, zeroer-1,-1): for j in range(n,oneser-1,-1): dp[i][j] = max(dp[i][j], dp[i-zeroer][j-oneser]+1) #print(dp) return dp[-1][-1]5.完全背包完全背包内物品可以⽆限取，01背包内物品每个物品只能取⼀次。01背包为了保证每个物品只取⼀次，所以取值时候是从后向前取的123for i in range(len(weight)):#

遍历物品 for j in range(target, nums[i]-1,-1):#遍历背包 dp[j] = max(dp[j], dp[j-nums[i]]+values[i])完全背包不同，可以重复取之前的值，从前往后取123for i in range(len(weight)):#

遍历物品 for j in range(nums[i], target+1):#遍历背包 dp[j] = max(dp[j], dp[j-nums[i]]+values[i])这道题必须外层是物品，内层是背包，这样计算出来的是排除顺序的，是组合，排列就需要反过来，⼀定要分的清楚这两种情况。1112class Solution: def change(self, amount: int, coins: List[int]) -> int: #完全背包问题 #dp[i]

为总⾦额i下组合数 #dp[j]+=dp[j-coins[i]] dp = [0]*(amount+1) dp[0] =1 #总⾦额0

只有⼀种组合情况 for i in range(len(coins)): for j in range(coins[i],amount+1): dp[j] += dp[j-coins[i]] #print(dp) return dp[-1]6.总结1）动态规划问题，类似就是爬楼梯问题，可以⼀次爬1阶，也可以⼀次爬两阶，这样在爬i阶情况下有多少中情况，应该⽤dp[i]表⽰i台阶下情况数，为dp[i-1]+dp[i-2]当不是确定1介两阶情况，就可以抽象成数组nums这样就需要将每个nums，加到⼀起 即 dp[i]+= dp[i-num[j]]需要遍历数组将所有情况加起来。2）之后就出来了背包问题，这相当于在爬楼梯情况下，加⼊了台阶数还会变化。背包问题还是挺难的。01背包都是遍历背包时候都是从后向前遍历的，为了保证物品只⽤⼀次，这和01背包定义有关系。完全背包没有这样的限制，所以应该从前向后遍历。这⾥涉及到排列组合区别，带来外内层遍历选择问题，明天应该就看到了。

2023年8月1日发(作者：)

⼒扣刷题-python-动态规划-1（动态规划、01背包问题、完全背包问题）⽂章⽬录1.动态规划动态规划 是由前⼀个状态推导出贪⼼算法 是直接取局部最优动态规划需要直到状态转移公式解题过程分为5步1. 确定dp数组（dp table）以及下标的含义2. 确定递推公式3. dp数组如何初始化4. 确定遍历顺序5. 举例推导dp数组2.简单和中等题其实也不⽤写dp数组，这道题就可以解出来，但是这道题还是⽤了动态规划的思想，每个数之间是有关系的12345678class Solution: def fib(self, n: int) -> int: if n<2:return n a, b = 0, 1 for i in range(n-1): a=a+b a,b=b,a return b这道题同上⼀道题class Solution: def climbStairs(self, n: int) -> int: #每次爬台阶相当于是 n-1情况

和n-2情况和， dp=[] for i in range(n): if i<2: (i+1) else: dp[0]+=dp[1] dp[0],dp[1]=dp[1],dp[0] return dp[-1]进阶版的爬楼梯class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: #dp[i]为某⼀层花费 dp[i] =min(dp[i-1] dp[i-2])+cost[i] #dp[0]=1 dp[1]=100 dp = [0]*len(cost) #提前配置好空间，再赋值会快很多 for i in range(len(cost)): if i <2: dp[i]=cost[i] else:dp[i]= min(dp[i-1],dp[i-2]) + cost[i] return min(dp[-2:])这道题和爬楼梯类似，不过是⼀个⼆维的class Solution: def uniquePaths(self, m: int, n: int) -> int: #第mn

⾏肯定是

第m-1 n

⾏

和第m n-1⾏移动过来的 #dp表⽰mn位置的条数 dp[m][n] #初始化 m=0位置为1 n=0位置为1

因为边上只有⼀条路径可以⾛ dp= [[1]*n for _ in range(m)] 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]class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: #同前⼀道题，但是加⼊了障碍物，所以要将障碍物位置变为0，

dp = obstacleGrid for i in range(len(dp)): for j in range(len(dp[0])): if not dp[i][j]-1: dp[i][j]=0 elif not i and not j :dp[i][j]=1 else: dp[i][j] =(dp[i-1][j] if i>0 else 0)+(dp[i][j-1] if j >0 else 0) return dp[-1][-1]这道题的确不好想，⽽且 是个⼆维的循环，以后在动态规划，可能会经常⽤到。class Solution: def integerBreak(self, n: int) -> int: #第n个

相当于

第n

分解成 n-i和i乘积

和dpn-i和i乘积⽐较

选最⼤的 #虽然n是从2开始的

相当于只有n-2+1

个

但是为了遍历⽅便扩充成n个 dp= [_+1 for _ in range(n)] for i in range(n): for j in range(1,i): dp[i] = max(dp[i] , max(dp[i-j]*j,(i-j)*j)) #print(dp) return dp[-1] if n>=4 else n-1 1112class Solution: def numTrees(self, n: int) -> int: #dp

为n情况下⼆叉搜索树的个数 #dp[i] +=dp[i-j-1]dp[j] for j in range(i) dp= [0]*(n+1)

for i in range(n+1): if i < 2: dp[i]=1 else: for j in range(i):dp[i] +=dp[i-j-1]*dp[j] #print(dp)

return dp[-1]3.01背包问题基础1.01背包基础背包问题是个啥，我⼀直很好奇，今天终于看到这⾥了，先看下基础理论。171819# -*- coding: gbk -*-#暴⼒解法nmax=3nlist=[15,20,30]nweigt=[1,3,4]res= []def backtracking(n,weight,hw): if not n - nmax :return (hw) for i in [0,1]: if i: #选择

hw+= nlist[n-1] weight-=nweigt[n-1]

backtracking(n+1,weight,hw)

backtracking(1,4,0)print('所有可能的情况为：',res)print('可以放⼊最⼤为：',max(res))暴⼒解法肯定是不可取的，⽤的时间为o（2^n)当这个物体n特别多的时候，这样就太浪费时间了，肯定暴⼒的⽅法是不可取的2.01背包问题的动态规划（⼆维数组）1）定义2）递推关系如果某⼀⾏ 即某⼀个物品i 在j⼩于weight[i]时候，直接取 dp[i-1][j]如果⼤于weight[i]时候，就可以⽐较他放⼊与不放⼊的总重量的⼤⼩，肯定选最⼤的那个dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])3）初始化全部初始化为0，但是每次都是和i-1⽐较，所以要初始化i=0⾏4）遍历顺序选择⼀⾏⼀⾏遍历，就是⼀个物品⼀个物品来5）对⽐dp数组并修改程序1112weight=[1,3,4]value=[15,20,30]n=4dp= [[0]*(n+1) for _ in range(len(weight))]for j in range(n+1): #初始化第⼀⾏ if j>=weight[0]: dp[0][j] = value[0]for i in range(1,len(weight)): for j in range(1,n+1): if j

表⽰j表⽰此时的还剩下的重量 dp表⽰总价值#dp[j] =max(dp[j-weight[i]]+value[i],dp[j])weight=[1,3,4]value=[15,20,30]n=4dp= [0 for _ in range(n+1)]for i in range(len(weight)): for j in range(n,weight[i]-1,-1): #这⾥⽤了从⼤到⼩的顺序，⽽且只取到物品的⼤⼩，前⾯全是原来的

很巧妙 dp[j] =max(dp[j-weight[i]] +value[i],dp[j])print(dp)4.01背包问题这道题就是典型的背包问题class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums)%2: return False target=sum(nums)//2 pd=[0]*(target+1) for i in range(len(nums)): for j in range(target,nums[i]-1,-1): pd[j]=max(pd[j-nums[i]]+nums[i],pd[j]) if not pd[-1]-target :return True else:return False1112class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: #把⽯头分成两堆

让两堆的数量尽量接近

#这就变成01背包问题，就是让选出数量尽量接近平均数 sumer = sum(stones) target = sumer//2 dp = [0]*(target+1) for i in range(len(stones)): for j in range(target, stones[i]-1,-1): dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]) #print(dp,sumer) return sumer-2*dp[-1]111213class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: #dp为填满target⼤⼩的可能情况 suber =(sum(nums)-target) target = suber//2 if suber%2 or target<0 :return 0 dp = [0]*(target+1) dp[0]=1 #装满容量为0的背包，有1种⽅法，就是装0件物品。 for i in range(len(nums)): for j in range(target,nums[i]-1,-1): dp[j] +=dp[j-nums[i]] return dp[-1]111213class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: #dp

为i个0和j个1情况下最⼤⼦集 dp = [[0]*(n+1) for _ in range(m+1)]

for strer in strs: zeroer= ('0') oneser= ('1') for i in range(m, zeroer-1,-1): for j in range(n,oneser-1,-1): dp[i][j] = max(dp[i][j], dp[i-zeroer][j-oneser]+1) #print(dp) return dp[-1][-1]5.完全背包完全背包内物品可以⽆限取，01背包内物品每个物品只能取⼀次。01背包为了保证每个物品只取⼀次，所以取值时候是从后向前取的123for i in range(len(weight)):#

遍历物品 for j in range(target, nums[i]-1,-1):#遍历背包 dp[j] = max(dp[j], dp[j-nums[i]]+values[i])完全背包不同，可以重复取之前的值，从前往后取123for i in range(len(weight)):#

遍历物品 for j in range(nums[i], target+1):#遍历背包 dp[j] = max(dp[j], dp[j-nums[i]]+values[i])这道题必须外层是物品，内层是背包，这样计算出来的是排除顺序的，是组合，排列就需要反过来，⼀定要分的清楚这两种情况。1112class Solution: def change(self, amount: int, coins: List[int]) -> int: #完全背包问题 #dp[i]

为总⾦额i下组合数 #dp[j]+=dp[j-coins[i]] dp = [0]*(amount+1) dp[0] =1 #总⾦额0

只有⼀种组合情况 for i in range(len(coins)): for j in range(coins[i],amount+1): dp[j] += dp[j-coins[i]] #print(dp) return dp[-1]6.总结1）动态规划问题，类似就是爬楼梯问题，可以⼀次爬1阶，也可以⼀次爬两阶，这样在爬i阶情况下有多少中情况，应该⽤dp[i]表⽰i台阶下情况数，为dp[i-1]+dp[i-2]当不是确定1介两阶情况，就可以抽象成数组nums这样就需要将每个nums，加到⼀起 即 dp[i]+= dp[i-num[j]]需要遍历数组将所有情况加起来。2）之后就出来了背包问题，这相当于在爬楼梯情况下，加⼊了台阶数还会变化。背包问题还是挺难的。01背包都是遍历背包时候都是从后向前遍历的，为了保证物品只⽤⼀次，这和01背包定义有关系。完全背包没有这样的限制，所以应该从前向后遍历。这⾥涉及到排列组合区别，带来外内层遍历选择问题，明天应该就看到了。