【LeetCode 刷题】动态规划(2)-背包问题

此博客为《代码随想录》动态规划章节的学习笔记，主要内容为动态规划背包问题的相关题目解析。

文章目录

• 一、01背包
• • 理论基础
  • 416. 分割等和子集
  • 1049. 最后一块石头的重量II
  • 494. 目标和
  • 474. 一和零
• 二、完全背包
• • 理论基础
  • 518. 零钱兑换II
  • 377. 组合总和 Ⅳ
  • 70. 爬楼梯（进阶）
  • 322. 零钱兑换
  • 279. 完全平方数
  • 139. 单词拆分
• 三、多重背包
• • 理论基础

一、01背包

理论基础

问题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 c[i]，得到的价值是 v[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维 dp

• 状态定义：dp[i][j] 表示 使用前 i 个物品，在背包容量为 j 时最大的价值总和
• 递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + v[i])
• 遍历顺序：先遍历物品，再遍历背包容量，均为正序（从左到右、从上到下）

一维 dp

• 状态定义：dp[j] 表示 容量为 j 的背包，所背的物品价值最大值
• 递推公式：dp[j] = max(dp[j], dp[j - c[i]] + v[i])
• 遍历顺序：先遍历物品，再遍历背包容量，正序遍历物品，倒序遍历背包容量（防止上一层的值被覆盖）

注意：定义 dp 数组时，额外多添加一行一列，即从考虑前 0 个物品、背包容量为 0 开始计算，可以减少初始化操作；由于 dp 数组添加了一行物品状态，递推公式中，对 c 和 v 进行索引时，下标要减 1。

416. 分割等和子集

题目链接

方法1：完全仿照 0-1 背包

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_num = sum(nums)
        if sum_num % 2 == 1:
            return False
        m = len(nums)  # 视作物品数量
        n = sum_num // 2  # 视作背包容量
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if j >= nums[i-1]:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n] == n

• 背包容量为数组总和的一半，物品的价值和重量都是 nums[i]
• 返回是否能够恰好装满背包，即 dp[m][n] == n

方法二：适配题目

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_num = sum(nums)
        if sum_num % 2 == 1:
            return False
        m = len(nums)  # 视作物品数量
        n = sum_num // 2  # 视作背包容量
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                if j >= nums[i-1]:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 状态定义：dp 数组直接定义为布尔量，dp[i][j] 表示 使用前 i 个物品是否能够达到目标和 j
• 递推公式：dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]] ，dp[i-1][j] 即不选 num[i-1]，dp[i-1][j-nums[i-1]] 即选 num[i-1]，两者取并集
• dp[0][0] 初始化为 True
• 注意：上述代码中对 n 的遍历从 0 开始（其实是把初始化过程结合到递推过程中；把第一列均初始化为 True 后 n 的遍历也可从 1 开始）

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

题目链接

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        m = len(stones)
        n = sum(stones) // 2
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if j >= stones[i-1]:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1])
                else:
                    dp[i][j] = dp[i-1][j]
        return sum(stones) - 2 * dp[m][n]

• 背包容量为数组总和的一半（下取整），物品的价值和重量都是 stones[i]
• 另一部分的重量为 sum(stones) - dp[m][n]，返回两部分重量差，即 sum(stones) - 2 * dp[m][n]

494. 目标和

题目链接

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums) - abs(target)
        if s < 0 or s % 2 == 1:
            return 0
        m = len(nums)
        n = s // 2
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        print(m, n)
        dp[0][0] = 1
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                if j >= nums[i-1]:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 设添加正号和添加负号的原始数字的和分别为 p 和 q，则 p + q = sum，p - q = target，因此即找目标和为 $\frac{sum-target}{2}$ 或 $\frac{sum+target}{2}$ 的方案数
• $\frac{sum-target}{2}$ 和 $\frac{sum+target}{2}$ 二者等价，均可作为背包容量，但为降低复杂度，希望选择小的数，因此上述题解中选择 $\frac{sum-abs(target)}{2}$ 作为背包容量
• 递推公式：dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]，即选或不选 nums[i-1] 的方案数之和
• 初始化：dp[0][0] 初始化为 1

474. 一和零

题目链接

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        m_ = len(strs)  # 背包容量
        def cal(s: str) -> (int, int):
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            return cnt0, cnt1
        
        dp = [[[0 for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(m_ + 1)]
        for i in range(1, m_ + 1):
            zero, one = cal(strs[i-1])
            for j in range(0, m + 1):
                for k in range(0, n + 1):
                    if j >= zero and k >= one:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one] + 1)
                    else:
                        dp[i][j][k] = dp[i-1][j][k]
        return dp[m_][m][n]

• 两个约束维度的背包问题，计算最终选择物品数量的最大值
• 状态定义：dp[i][j][k] 表示使用前 i 个物品，0 和 1 的数量分别不超过 j 和 k，所能选择的最多物品数量
• 递推公式：dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one] + 1)
• 注意：遍历 0 和 1 数量时，要从 0 开始。因为物品有两个维度的属性，可能只具有 0 或者只具有 1，因此对于另一个维度限制在 0 的情况也有可能是合法的

二、完全背包

理论基础

问题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 c[i]，得到的价值是 v[i]。每件物品有无数个（即可以放入多次），求解将哪些物品装入背包里物品价值总和最大。

二维 dp

• 状态定义：dp[i][j] 表示 使用前 i 个物品，在背包容量为 j 时最大的价值总和
• 递推公式：dp[i][j] = max(dp[i-1][j], dp[i][j-c[i]] + v[i])；和 01 背包唯一的区别在于选择当前物品时，只减少背包容量，物品状态仍然在第 i 层，即 dp[i][j-c[i]] + v[i]；01 背包选择当前物品后，物品状态会转到上一层，即 dp[i-1][j-c[i]] + v[i]
• 遍历顺序：先遍历物品，再遍历背包容量，均为正序（从左到右、从上到下）

一维 dp

• 状态定义：dp[j] 表示 容量为 j 的背包，所背的物品价值最大值
• 递推公式：dp[j] = max(dp[j], dp[j - c[i]] + v[i])；与 01 背包相同
• 遍历顺序：先遍历物品，再遍历背包容量，均为正序；01 背包要倒叙遍历背包容量

518. 零钱兑换II

题目链接

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        m = len(coins)
        n = amount
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = 1
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                if j >= coins[i-1]:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 背包容量为目标钱数 amount，物品重量和价值均为 coins[i]，求总方案数（组合数）
• 递归公式：dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
• 初始化：dp[0][0] = 1，遍历背包容量要从 0 开始

377. 组合总和 Ⅳ

题目链接

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        m = len(nums)
        n = target
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = 1
        for j in range(0, n + 1):
            for i in range(1, m + 1):
                if j >= nums[i-1]:
                    dp[i][j] = dp[i-1][j] + dp[m][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 背包容量为目标值 target，物品重量和价值均为 nums[i]，求总方案数（排序数）
• 与上题相比，本题选择物品的顺序不同也会被统计为不同方案，需要修改的点如下：
  • 先遍历背包容量、再遍历物品；完全背包问题为先遍历物品、再遍历背包容量，所有统计的方案中的物品顺序均为原物品序列的子序列
  • 递推公式在选择当前物品时，表示为 dp[m][j-nums[i-1]]，即考虑所有的物品，允许序列在后面的物品在之前已经被选择；完全背包问题为 dp[m][j-nums[i-1]

70. 爬楼梯（进阶）

题目链接

进阶：如果每次你可以爬至多 m (1 <= m < n) 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• 代码与上题基本完全相同，同样为求排列数

322. 零钱兑换

题目链接

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m = len(coins)
        n = amount
        dp = [[inf for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = 0
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                if j >= coins[i-1]:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n] if dp[m][n] != inf else -1

• 背包容量为目标钱数 amount，物品重量和价值均为 coins[i]，求最少选择的物品数
• 递推公式：dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)
• 初始化：dp[0][0] = 0，其余元素为 inf；遍历背包容量是从 0 开始
• 注意：题目要求如果不存在方案返回 -1，但为了 min() 能够正常工作且代码逻辑尽可能简单，dp 数组中的元素值应初始化为 inf 而非 -1

279. 完全平方数

题目链接

class Solution:
    def numSquares(self, n: int) -> int:
        m = int(sqrt(n))
        dp = [[inf for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = 0
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                weight = i * i
                if j >= weight:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-weight] + 1)
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 背包容量为目标 n，物品的重量和价值依此均为 [1, 4, 9, ...]
• 其余思路和上题相同

139. 单词拆分

题目链接

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        m = len(wordDict)
        n = len(s)
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(0, n + 1):
            for i in range(1, m + 1):
                weight = len(wordDict[i-1])
                if j >= weight and s[j-weight:j] == wordDict[i-1]:
                    dp[i][j] = dp[i-1][j] or dp[m][j-weight]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

• 背包容量为拼接单词的长度，物品价值为 wordDict[i] ，物品重量为 len(wordDict[i])，求是否能够装满背包
• 一个物品可以用多次，且需要考虑物品使用的顺序（排序数），因此整体代码结构类似于 “322. 零钱兑换”
  • 先遍历背包容量、再遍历物品
  • 选择当前物品的结果，表示为 dp[m][j-weight]，并非 dp[i][j-weight]
• 递推公式：dp[i][j] = dp[i-1][j] or dp[m][j-weight]
• 额外添加限制：s[j-weight:j] == wordDict[i-1] ，才能够使用当前物品

三、多重背包

理论基础

问题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 c[i]，得到的价值是 v[i]。每件物品可用的数量为 m[i]，求解将哪些物品装入背包里物品价值总和最大。

思路：将每个物品的 m[i] 件实例展开，即转换为 01背包问题

实现：把每种商品的个数在最内层循环遍历一遍

for i in range(m):
    for j in range(n):
        for k in range(1, nums[i] + 1):
            # 遍历 k，如果已经大于背包容量直接跳出循环
            if k * weights[i] > j:
                break
            dp[j] = max(dp[j], dp[j - weights[i] * k] + values[i] * k)