前言

背包问题实际上是动态规划的一种经典应用,本文想通过介绍一种模板用于解决各种背包问题。

  • 模板统一采用二维数组来表示动态规划的状态,其中表示物品的价值(或体积、大小、重量等),表示背包的容量(或目标值)。
  • 行和列都增加了一位,即从1开始计数,一来可以避免边界检查,二来dp[...][target]变得有意义,而非dp[...][target-1],具体值和数组索引能够对上。根据不同题意来初始化dp,需要注意的是只要涉及到取物品的值,我们需要对索引减1,因为我们是从1开始计数的。

接下来分三种情况考虑动态规划中的状态转移表达式:

  1. 完全背包(每件物品可以无限使用):dp[i][j]=OPERATE(dp[i-1][j],dp[i][j-objs[i-1]])。这里的OPERATE可以是summaxor视具体的问题而定。第二个表达式的索引是i
    完全背包问题状态转移图示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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]
  2. 01背包(每件物品只可使用一次):dp[i][j]=OPERATE(dp[i-1][j],dp[i-1][j-objs[i-1]]),注意和完全背包问题的区别,第二个表达式的索引是i-1
    01背包问题状态转移图示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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]
  3. 完全背包排列:dp[i][j]=OPERATE(dp[i-1][j],dp[-1][j-objs[i-1]]),第二个表达式的索引是-1,也即最后一行。

    遍历行时的顺序也即访问每件物品的顺序,虽然物品顺序不作限制,但这里有个隐藏条件,遍历过的物品是不会再次访问的,也就是说,选择物品是组合问题,无论先选哪个后选哪个,只要都被选了,只能算作一种状态。
    这里归到第3类的问题仍然归属于完全背包范畴,但是它是求排列而非组合,即先拿A或者先拿B,或者拿了A,B之后还可以再次拿A。
    在前面的2类问题中,我们优先行或者优先列遍历对结果来说并没有影响,但在这里由于状态转移方程中每次都需最后一行参与计算,所以必须优先列遍历
    完全背包排列问题状态转移图示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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种物品中任选,每种物品可以无限取用恰好可以装满背包的组合数是多少?

1
2
3
4
5
6
7
8
9
10
11
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

问题转换:和完全背包的恰好装满问题一样,只不过是求排列数而非组合数。

1
2
3
4
5
6
7
8
9
10
11
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

问题转换:完全背包恰好装满,所需最少物品数。

1
2
3
4
5
6
7
8
9
10
11
12
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,所以可以确定数字的上限。

1
2
3
4
5
6
7
8
9
10
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语言采用此方法提交会超出时间限制,一个更好的办法是采用数学来解此题,会用到一个数学定理:四平方和定理

布尔值

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

问题转换:完全背包恰好装满,是否存在解决方案,单词用过之后可以再用,所以这里应该采用排列的策略。

1
2
3
4
5
6
7
8
9
10
11
12
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。

问题转换:从一堆物品中选出若干个,恰好能装满背包的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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维。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为xy,且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背包问题:给定一些石头和一个指定容量的背包,最多可以装多少重量的石头(不能超过背包容量)。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]