背包问题实际上是动态规划的一种经典应用,本文想通过介绍一种模板用于解决各种背包问题。
1
开始计数,一来可以避免边界检查,二来dp[...][target]
变得有意义,而非dp[...][target-1]
,具体值和数组索引能够对上。根据不同题意来初始化dp
,需要注意的是只要涉及到取物品的值,我们需要对索引减1,因为我们是从1开始计数的。接下来分三种情况考虑动态规划中的状态转移表达式:
完全背包(每件物品可以无限使用):dp[i][j]=OPERATE(dp[i-1][j],dp[i][j-objs[i-1]])
。这里的OPERATE
可以是sum
、max
、or
视具体的问题而定。第二个表达式的索引是i
。
1234567891011 | def bag_problem(self, bag: int, objs: List[int]) -> int: n=len(objs)+1 #将物品数量增加1,避免边界检查 #以下两行初始化dp状态 dp=[[xxx]*(bag+1) for _ in range(n)] dp[0][0]=xxx for i in range(1,n): for j in range(bag+1): dp[i][j]=dp[i-1][j] if j>=objs[i-1]: #涉及到物品的索引都需要减1 dp[i][j]=operate(dp[i-1][j],dp[i][j-objs[i-1]]) #注意第2项是i return dp[-1][-1] |
---|
01背包(每件物品只可使用一次):dp[i][j]=OPERATE(dp[i-1][j],dp[i-1][j-objs[i-1]])
,注意和完全背包问题的区别,第二个表达式的索引是i-1
。
1234567891011 | def bag_problem(self, bag: int, objs: List[int]) -> int: n=len(objs)+1 #将物品数量增加1,避免边界检查 #以下两行初始化dp状态 dp=[[xxx]*(bag+1) for _ in range(n)] dp[0][0]=xxx for i in range(1,n): for j in range(bag+1): dp[i][j]=dp[i-1][j] if j>=objs[i-1]: #涉及到物品的索引都需要减1 dp[i][j]=operate(dp[i-1][j],dp[i-1][j-objs[i-1]]) #注意第2项是i-1 return dp[-1][-1] |
---|
完全背包排列:dp[i][j]=OPERATE(dp[i-1][j],dp[-1][j-objs[i-1]])
,第二个表达式的索引是-1
,也即最后一行。
遍历行时的顺序也即访问每件物品的顺序,虽然物品顺序不作限制,但这里有个隐藏条件,遍历过的物品是不会再次访问的,也就是说,选择物品是组合问题,无论先选哪个后选哪个,只要都被选了,只能算作一种状态。 这里归到第3类的问题仍然归属于完全背包范畴,但是它是求排列而非组合,即先拿A或者先拿B,或者拿了A,B之后还可以再次拿A。 在前面的2类问题中,我们优先行或者优先列遍历对结果来说并没有影响,但在这里由于状态转移方程中每次都需最后一行参与计算,所以必须优先列遍历。
1234567891011 | def bag_problem(self, bag: int, objs: List[int]) -> int: n=len(objs)+1 #将物品数量增加1,避免边界检查 #以下两行初始化dp状态 dp=[[xxx]*(bag+1) for _ in range(n)] dp[0][0]=xxx for j in range(bag+1): #内外循环颠倒,按列遍历 for i in range(1,n): dp[i][j]=dp[i-1][j] if j>=objs[i-1]: #涉及到物品的索引都需要减1 dp[i][j]=operate(dp[i-1][j],dp[-1][j-objs[i-1]] #第2项是-1,表示最后一行 return dp[-1][-1] |
---|
下面,让我们使用该模板来解决力扣上的各种背包问题。
现在问题的关键就在于把实际问题抽象化为背包问题中的哪一类,然后套用模板即可。 在以下问题中,模板中的二维数组均可优化为一维数组以降低空间复杂度。不用加重记忆负担去考虑什么时候该顺序遍历,什么时候该逆序遍历,以及行列遍历顺序能不能颠倒。当你了解了这个模板的含义,知道动态规划是如何在二维数组上实现的,这些问题都可以迎刃而解。
从n种物品中任选,每种物品可以无限取用
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10] 输出: 1
问题转换:从n种物品中任选,每种物品可以无限取用,恰好可以装满背包的组合数是多少?
1234567891011 | def change(self, amount: int, coins: List[int]) -> int: n=len(coins)+1 dp=[[0]*(amount+1) for _ in range(n)] dp[0][0]=1 for i in range(1,n): for j in range(amount+1): dp[i][j]+=dp[i-1][j] if j>=coins[i-1]: # dp[i][j]=sum(dp[i-1][j],dp[i][j-objs[i-1]]) dp[i][j]+=dp[i][j-coins[i-1]] return dp[-1][-1] |
---|
给你一个由不同整数组成的数组nums
,和一个目标整数target
。请你从nums
中找出并返回总和为target
的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1:
输入:nums = [1,2,3], target = 4 输出:7 解释: 所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意,顺序不同的序列被视作不同的组合。
示例 2:
输入:nums = [9], target = 3 输出:0
问题转换:和完全背包的恰好装满问题一样,只不过是求排列数而非组合数。
1234567891011 | def combinationSum4(self, nums: List[int], target: int) -> int: n=len(nums)+1 dp=[[0]*(target+1) for _ in range(n)] dp[0][0]=1 for j in range(target+1): #内外循环颠倒,按列遍历 for i in range(1,n): dp[i][j]+=dp[i-1][j] if j>=nums[i-1]: #这里是-1,不是i-1。dp[i][j]=sum(dp[i-1][j],dp[-1][j-objs[i-1]]) dp[i][j]+=dp[-1][j-nums[i-1]] return dp[-1][-1] |
---|
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3 输出:-1
示例 3:
输入:coins = [1], amount = 0 输出:0
示例 4:
输入:coins = [1], amount = 1 输出:1
示例 5:
输入:coins = [1], amount = 2 输出:2
问题转换:完全背包恰好装满,所需最少物品数。
123456789101112 | def coinChange(self, coins: List[int], amount: int) -> int: n=len(coins)+1 dp=[[0]*(amount+1) for _ in range(n)] for j in range(1,amount+1): #初始化为极值 dp[0][j]=float('inf') for i in range(1,n): for j in range(amount+1): dp[i][j]=dp[i-1][j] #求dp[i-1][j]和dp[i][j-coins[i-1]]+1的较小值,这里是赋值而非累加 if j>=coins[i-1]: # dp[i][j]=min(dp[i-1][j],dp[i][j-objs[i-1]]) dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1) return -1 if dp[-1][-1]==float('inf') else dp[-1][-1] |
---|
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ,返回和为 n 的完全平方数的最少数量。 完全平方数是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13 输出:2 解释:13 = 4 + 9
问题转换:完全背包恰好装满,所需最少物品数。把正整数n抽象化为背包容量,从1开始的正整数抽象化为物品,其重量是值的平方。它的平方不能超过n,所以可以确定数字的上限。
12345678910 | def numSquares(self, n: int) -> int: m=math.floor(n**0.5) #最大物品的值 dp=[[float('inf')]*(n+1) for _ in range(m+1)] dp[0][0]=0 for i in range(1,m+1): for j in range(n+1): dp[i][j]=dp[i-1][j] if j>=i**2: dp[i][j]=min(dp[i-1][j],dp[i][j-i**2]+1) return dp[-1][-1] |
---|
注意:python语言采用此方法提交会超出时间限制,一个更好的办法是采用数学来解此题,会用到一个数学定理:四平方和定理。
给你一个整数数组cost
和一个整数target
。请你返回满足如下规则可以得到的最大整数:
i + 1
)的成本为cost[i]
(cost
数组下标从 0 开始)。
target
。
由于答案可能会很大,请你以字符串形式返回。 如果按照上述要求无法得到任何整数,请你返回 “0” 。
示例 1:
输入:cost = [4,3,2,5,6,7,2,5,5], target = 9 输出:”7772” 解释:添加数位 ‘7’ 的成本为 2 ,添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 23+ 31 = 9 。 “977” 也是满足要求的数字,但 “7772” 是较大的数字。 数字 成本 1 -> 4 2 -> 3 3 -> 2 4 -> 5 5 -> 6 6 -> 7 7 -> 2 8 -> 5 9 -> 5
问题转换:每个物品体积不一样,完全背包恰好装满,最多可以装多少个物品。数字能选择的越多,必然能得到的数字越大,同时,我们是从1-9
开始选择,也就是从数值的小到大,如果确定选择了这个数,也必然是目前最大的,那肯定放在最高位,得到的整数最大。
可完全套用完全背包模板,只需把operate
抽象化为一个函数,这个函数类似于max
函数,不过更高级,它比较2个值,在能恰好装满背包的前提下,谁组成的数字更大。
123456789101112131415161718192021222324252627 | def largestNumber(self, cost: List[int], target: int) -> str: def maxValue(a,b,v): if a is None and b is None: # 两种方案都不可行,返回None return None if b is None: # 其中一种不行,就直接返回另一种 return a b=v+b if a is None: return b n1,n2=len(a),len(b) # 两种都可以,比较谁的数值更大 if n1>n2: return a elif n1<n2: return b return max(a,b) n=len(cost) dp=[['']*(target+1) for _ in range(n+1)] # 标准完全背包模板,只是把operate换成了自定义函数maxValue for j in range(1,target+1): dp[0][j]=None for i in range(1,n+1): for j in range(target+1): dp[i][j]=dp[i-1][j] if j>=cost[i-1]: dp[i][j]=maxValue(dp[i-1][j],dp[i][j-cost[i-1]],str(i)) if dp[-1][-1] is None: return "0" return dp[-1][-1] |
---|
给定一个非空字符串 s 和一个包含非空单词的列表wordDict
,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
示例 1:
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2:
输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词。
示例 3:
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
问题转换:完全背包恰好装满,是否存在解决方案,单词用过之后可以再用,所以这里应该采用排列的策略。
123456789101112 | def wordBreak(self, s: str, wordDict) -> bool: n=len(wordDict)+1 dp=[[False]*(len(s)+1) for _ in range(n)] dp[0][0]=True for j in range(len(s)+1): #内外循环颠倒,按列遍历(单词可以不在乎顺序,和排列类似) for i in range(1,n): dp[i][j]=dp[i-1][j] if j>=len(wordDict[i-1]) and s[j-len(wordDict[i-1]):j]==wordDict[i-1]: #这里是-1,不是i-1。 # dp[i][j]=or(dp[i-1][j],dp[-1][j-objs[i-1]]) dp[i][j]|=dp[-1][j-len(wordDict[i-1])] return dp[-1][-1] |
---|
从n件物品中任选,每件物品只可取用一次
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例:
输入:nums: [1, 1, 1, 1, 1], S: 3 输出:5 解释: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 一共有5种方法让最终目标和为3。
问题转换:从一堆物品中选出若干个,恰好能装满背包的方案数。
12345678910111213141516171819 | def findTargetSumWays(self, nums: List[int], t: int) -> int: s=sum(nums) if t>s: return 0 t+=s if t%2!=0: return 0 t=t//2 #获取目标值,转换为01背包问题 n=len(nums)+1 dp=[[0]*(t+1) for _ in range(n)] dp[0][0]=1 for i in range(1,n): for j in range(t+1): dp[i][j]+=dp[i-1][j] if j>=nums[i-1]: # 和完全背包问题不同之处:这里是i-1。 # dp[i][j]=sum(dp[i-1][j],dp[i-1][j-objs[i-1]]) dp[i][j]+=dp[i-1][j-nums[i-1]] return dp[-1][-1] |
---|
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
输入:strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3 输出:4 解释:最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ,因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
示例 2:
输入:strs = [“10”, “0”, “1”], m = 1, n = 1 输出:2 解释:最大的子集是 {“0”, “1”} ,所以答案是 2 。
问题转换:01背包恰好装满,最多可以装多少个物品。注意这里的物品体积可以看作是由0
的个数和1
的个数2个维度构成的,仍然是01背包问题,只不过将物品的1维变成了2维。
123456789101112131415161718192021 | def findMaxForm(self, strs, m: int, n: int) -> int: nums = [] for s in strs: num = [0,0] for c in s: if ord(c) - ord('0') == 0: num[0]+=1 else: num[1]+=1 nums.append(num) #转换成01背包问题 l = len(nums) + 1 dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(l)] for i in range(1,l): for a in range(m + 1): for b in range(n + 1): dp[i][a][b] = dp[i - 1][a][b] if a >= nums[i - 1][0] and b >= nums[i - 1][1]: # dp[i][j]=max(dp[i-1][j],dp[i-1][j-objs[i-1]]) dp[i][a][b] = max(dp[i][a][b],dp[i - 1][a - nums[i - 1][0]][b - nums[i - 1][1]] + 1) return dp[-1][-1][-1] |
---|
有一堆石头,用整数数组stones
表示。其中stones[i]
表示第i
块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为x
和y
,且x <= y
。那么粉碎的可能结果如下:
如果x == y
,那么两块石头都会被完全粉碎;
如果x != y
,那么重量为 x 的石头将会完全粉碎,而重量为y
的石头新重量为y-x
。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。
示例 1:
输入:stones = [2,7,4,1,8,1] 输出:1 解释: 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1], 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1], 组合 2 和 1,得到 1,所以数组转化为 [1,1,1], 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
示例 2:
输入:stones = [31,26,33,21,40] 输出:5
问题转换:如果把石头分成两组,使两组的重量尽可能相同,那么最终剩下的重量就越小。所以尽可能使2组的石头重量倾向于总重量的一半,问题变成01背包问题:给定一些石头和一个指定容量的背包,最多可以装多少重量的石头(不能超过背包容量)。
123456789101112 | def lastStoneWeightII(self, stones: List[int]) -> int: n=len(stones)+1 s=sum(stones) t=s//2 dp=[[0]*(t+1) for _ in range(n)] for i in range(1,n): for j in range(t+1): dp[i][j]=dp[i-1][j] if j>=stones[i-1]: dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]) return s-2*dp[-1][-1] |
---|
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
问题转换:从nums
选n个数字能否凑齐s//2
。
1234567891011121314151617 | def canPartition(self, nums: List[int]) -> bool: s=sum(nums) if s%2!=0: return False if max(nums)*2>s: return False s=s//2 #转换成01背包问题 n=len(nums)+1 dp=[[False]*(s+1) for _ in range(n)] dp[0][0]=True for i in range(1,n): for j in range(s+1): dp[i][j]=dp[i-1][j] if j>=nums[i-1]: # dp[i][j]=or(dp[i-1][j],dp[i-1][j-objs[i-1]]) dp[i][j]|=dp[i-1][j-nums[i-1]] return dp[-1][-1] |
---|