一个模板搞定各种背包问题
前言
背包问题实际上是动态规划的一种经典应用，本文想通过介绍一种模板用于解决各种背包问题。
- 模板统一采用二维数组来表示动态规划的状态，其中行表示物品的价值（或体积、大小、重量等），列表示背包的容量（或目标值）。
- 行和列都增加了一位，即从
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种物品中任选，每种物品可以无限取用
方案数
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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] |
|---|
特例：求排列非组合
377. 组合总和 Ⅳ
给你一个由不同整数组成的数组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] |
|---|
最值
322. 零钱兑换
给定不同面额的硬币 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] |
|---|
279. 完全平方数
给定正整数 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语言采用此方法提交会超出时间限制，一个更好的办法是采用数学来解此题，会用到一个数学定理：四平方和定理。
1449. 数位成本和为目标值的最大数字
给你一个整数数组cost和一个整数target。请你返回满足如下规则可以得到的最大整数：
- 给当前结果添加一个数位（
i + 1）的成本为cost[i]（cost数组下标从 0 开始）。 - 总成本必须恰好等于
target。 - 添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。 如果按照上述要求无法得到任何整数，请你返回 “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] |
|---|
布尔值
139. 单词拆分
给定一个非空字符串 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] |
|---|
01背包
从n件物品中任选，每件物品只可取用一次
方案数
494. 目标和
给定一个非负整数数组，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] |
|---|
最值
474. 一和零
给你一个二进制字符串数组 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] |
|---|
1049. 最后一块石头的重量 II
有一堆石头，用整数数组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] |
|---|
布尔值
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 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] |
|---|
腾讯云开发者
