多重背包、分组背包与区间DP——从一维决策到二维合并的思维跃迁
第19课我们学过了0-1背包和完全背包，但面试中背包问题远不止这两种。多重背包、分组背包、二维费用背包是进阶面试的高频变体。而区间DP则是另一种完全不同的思维模式——它不是逐个物品决策，而是考虑如何合并相邻区间。
题目描述：给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币数。每种硬币可以重复使用。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for j in range(coin, amount + 1):
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1时间复杂度：O(n × amount)，空间复杂度：O(amount)
coin 到 amount（正序），这与0-1背包的倒序不同。正序允许同一物品被多次选取。这是背包DP最核心的区别。题目描述：给定一个非负整数数组 nums 和一个目标值 target，给每个数前面添加 + 或 -，使得结果等于 target，求有多少种方法。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
# 边界检查
if abs(target) > total or (target + total) % 2 != 0:
return 0
bag = (target + total) // 2
dp = [0] * (bag + 1)
dp[0] = 1
for num in nums:
for j in range(bag, num - 1, -1): # 倒序! 0-1背包
dp[j] += dp[j - num]
return dp[bag]时间复杂度：O(n × bag)，空间复杂度：O(bag)
abs(target) > total 或 (target+total)为奇数 时直接返回0。题目描述：有 n 个气球，编号为 0 到 n-1，每个气球上标有一个数字。戳破气球 i 可以获得 nums[left] × nums[i] × nums[right] 个硬币。求戳破所有气球能获得的最大硬币数。
nums[i] × nums[k] × nums[j]。这样左边 [i,k] 和右边 [k,j] 是独立的子问题！
dp[i][j] = 戳破开区间 (i,j) 内所有气球的最大收益。i和j是不被戳的边界。
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]×nums[k]×nums[j])，其中 i < k < j
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
# 加入虚拟边界
arr = [1] + nums + [1]
m = n + 2
dp = [[0] * m for _ in range(m)]
# 区间长度从2开始（至少要有两个边界）
for length in range(2, m):
for i in range(m - length):
j = i + length
# 枚举最后戳的气球
for k in range(i + 1, j):
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j])
return dp[0][m - 1]时间复杂度：O(n³)，空间复杂度：O(n²)
dp[i][j] 表示区间 [i,j] 上的最优值；(2) 枚举区间内的分割点 k，将问题分为 [i,k] 和 [k,j]；(3) 填表顺序：区间长度从短到长。这个模式适用于矩阵链乘法、合并石子、最长回文子串等所有区间DP问题。每种物品有数量上限 s[i]，既不是0-1（只能选1个），也不是完全（无限选）。核心优化是二进制拆分：将 s[i] 个物品拆成 1, 2, 4, ..., 2^k, remainder 组，然后当成0-1背包处理。这样复杂度从 O(n × V × s) 降到 O(n × V × log s)。
# 多重背包 — 二进制拆分
def multi_knapsack(weights, values, counts, capacity):
dp = [0] * (capacity + 1)
for w, v, c in zip(weights, values, counts):
# 二进制拆分
k = 1
while c > 0:
take = min(k, c)
# 按0-1背包处理（倒序）
for j in range(capacity, take * w - 1, -1):
dp[j] = max(dp[j], dp[j - take * w] + take * v)
c -= take
k *= 2
return dp[capacity]物品被分为若干组，每组最多选一个。状态转移时对每组整体考虑：对于每个容量 j，枚举该组中选哪个物品。
# 分组背包
def group_knapsack(groups, capacity):
# groups[i] = [(w1,v1), (w2,v2), ...] 第i组的物品
dp = [0] * (capacity + 1)
for group in groups:
for j in range(capacity, -1, -1): # 倒序(每组只能选一个)
for w, v in group:
if j >= w:
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]dp[j] += dp[j-num]dp[i][j] 表示区间，枚举分割点，按长度填表