动态规划进阶：背包与区间问题

简介

动态规划（Dynamic Programming， DP）是解决复杂优化问题的核心算法范式。在掌握了基础的斐波那契数列、爬楼梯等线性DP问题后，我们进入更具挑战性的领域：背包问题与区间问题。这两类问题不仅是算法竞赛和面试中的常客，其背后蕴含的“状态定义”、“状态转移”和“空间优化”思想，更是解决众多实际工程问题的钥匙。

背包问题模拟了在有限资源（如背包容量）下进行选择以最大化价值的经典场景，其变体如0-1背包和完全背包是理解更复杂DP模型的基础。区间DP则专注于解决涉及序列或区间操作的问题，通过枚举区间长度和分割点，自底向上地构建更大区间的解。此外，状态机DP为处理具有多个状态和状态间转移规则的问题（如股票买卖）提供了清晰的框架。

本节将深入探讨这些高级DP模型。我们将从背包问题的状态压缩技巧讲起，分析其如何将二维空间优化至一维；接着解剖区间DP的通用模板，并通过经典例题展示其威力；最后，我们将引入状态机的概念，系统化地解决股票买卖系列问题。通过理论与实践的结合，旨在帮助读者建立解决复杂DP问题的系统性思维。

核心概念

0-1背包与完全背包

0-1背包 是背包问题的基础模型：给定 n 件物品和一个容量为 C 的背包，第 i 件物品的重量是 w[i]，价值是 v[i]。每件物品只能选择一次（0或1），求解将哪些物品装入背包可使总价值最大。

其经典二维状态定义为：dp[i][j] 表示考虑前 i 件物品，在背包容量为 j 时能获得的最大价值。状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。关键优化是空间压缩：将二维数组压缩为一维数组 dp[j]，并逆序遍历容量 j（从 C 到 w[i]），以确保每个物品只被计算一次。

完全背包 与0-1背包的唯一区别在于：每种物品有无限件可用。其状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])。在空间压缩后，只需将容量 j 的遍历改为正序（从 w[i] 到 C），这恰好允许了物品的重复选取。

区间DP模型

区间DP用于解决涉及序列或区间操作的问题，其核心思想是：先解决小区间的问题，再利用小区间的解合并出大区间的解。通常使用二维状态 dp[i][j] 表示区间 [i, j] 上的最优解或可行性。

通用模板是：先枚举区间长度 len，再枚举区间起点 i，从而得到区间终点 j = i + len - 1，最后枚举区间分割点 k (i <= k < j)，通过状态转移方程 dp[i][j] = best_of(dp[i][k] + dp[k+1][j] + cost) 来更新结果。这种“分治+记忆化”的思想是区间DP的灵魂。

状态机DP

状态机DP适用于问题本身包含多个离散状态，且状态之间根据某些条件或操作进行转移。我们通过定义多个DP数组，每个数组对应一个状态，并清晰地描述状态间的转移关系。最典型的例子是股票买卖问题，其中“持有股票”和“不持有股票”就是两个核心状态，买入、卖出、持有不动则是状态转移的操作。

上图展示了一个简化的股票买卖状态机。状态机DP让我们能够清晰地刻画所有可能的操作路径，并通过DP记录每个状态下的最优收益。

实战示例

示例1：0-1背包空间优化（分割等和子集）

问题「416. 分割等和子集」可以转化为0-1背包问题：给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。这等价于：是否存在一个子集，其和为 sum(nums)/2。

我们将目标总和 target 视为背包容量，每个数字 nums[i] 视为重量和价值相等的物品。问题转化为：是否能恰好装满容量为 target 的背包。

def canPartition(nums):
"""
判断是否可以将数组分割成两个和相等的子集。
使用0-1背包的空间优化解法（一维DP）。
"""
total_sum = sum(nums)
# 如果总和是奇数，不可能平分
if total_sum % 2 != 0:
return False
target = total_sum // 2
# dp[j] 表示是否存在子集的和恰好为 j
dp = [False] * (target + 1)
dp[0] = True  # 和为0总是可以（不选任何元素）
for num in nums:
# 必须逆序遍历！确保每个数字只被使用一次
for j in range(target, num - 1, -1):
# 状态转移：不选当前数字 dp[j] 或 选当前数字 dp[j-num]
dp[j] = dp[j] or dp[j - num]
# 提前终止优化：如果目标已经达成，直接返回
if dp[target]:
return True
return dp[target]
# 测试用例
if __name__ == "__main__":
print(canPartition([1, 5, 11, 5]))  # 输出: True (11 = 5+5+1)
print(canPartition([1, 2, 3, 5]))   # 输出: False

代码解析：我们使用一维布尔数组 dp。遍历每个数字 num 时，内层循环从 target 逆序到 num，这是0-1背包空间优化的关键。如果正序遍历，dp[j - num] 可能在本轮循环中已被更新（即物品被重复使用），这就变成了完全背包的逻辑。逆序保证了每个物品只被考虑一次。

示例2：区间DP（戳气球）

问题「312. 戳气球」是区间DP的经典难题。有 n 个气球，每个气球上标有一个数字 nums[i]。戳破第 i 个气球，你可以获得 nums[left] * nums[i] * nums[right] 个硬币，其中 left 和 right 是 i 的相邻气球序号。求能获得的最大硬币数量。

关键思路是逆向思考：定义 dp[i][j] 为戳破开区间 (i, j) 内所有气球能获得的最大硬币数（i 和 j 不戳破，视为边界）。我们在原数组首尾添加值为1的虚拟气球。

def maxCoins(nums):
"""
戳气球问题 - 区间DP解法。
dp[i][j] 表示戳破开区间 (i, j) 内所有气球能获得的最大硬币数。
"""
n = len(nums)
# 构建新数组，首尾添加1
balloons = [1] + nums + [1]
new_n = n + 2
dp = [[0] * new_n for _ in range(new_n)]
# 区间DP模板：枚举区间长度，长度至少为3（因为开区间(i,j)至少包含一个气球）
for length in range(3, new_n + 1):  # 区间长度
for i in range(0, new_n - length + 1):  # 区间起点 i
j = i + length - 1  # 区间终点 j
# 枚举最后被戳破的气球 k (i < k < j)
# 假设k是区间(i,j)内最后一个被戳破的，则其左右边界就是i和j
for k in range(i + 1, j):
total = balloons[i] * balloons[k] * balloons[j]
total += dp[i][k] + dp[k][j]  # 加上左右两个子区间的解
dp[i][j] = max(dp[i][j], total)
# 最终结果是戳破整个开区间(0, n+1)即所有原始气球
return dp[0][new_n - 1]
# 测试用例
if __name__ == "__main__":
print(maxCoins([3, 1, 5, 8]))  # 输出: 167
# 解释：最优顺序 [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
# 硬币：3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167

代码解析：这是标准的区间DP三层循环。最外层枚举区间长度，中间层枚举起点，最内层枚举分割点（即最后一个被戳破的气球）。dp[i][j] 由 dp[i][k] 和 dp[k][j] 合并而来，加上戳破气球 k 的得分 balloons[i]*balloons[k]*balloons[j]。逆向思考（定义开区间、最后戳破）是简化问题的关键。

示例3：状态机DP（买卖股票的最佳时机 IV）

问题「188. 买卖股票的最佳时机 IV」是状态机DP的集大成者：给定一个整数数组 prices 表示股票价格，你最多可以完成 k 笔交易（买+卖算一笔），求最大利润。我们需要两个状态：“持有股票”和“未持有股票”，但交易次数限制增加了维度。

def maxProfit(k, prices):
"""
最多完成k笔交易的最大利润 - 状态机DP通用解法。
"""
n = len(prices)
if n == 0 or k == 0:
return 0
# 如果k很大，相当于无限交易，可以用贪心简化，防止DP数组过大
if k >= n // 2:
return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))
# 状态定义：
# dp[i][j][0] 第i天，最多完成了j笔交易，手上不持有股票的最大利润
# dp[i][j][1] 第i天，最多完成了j笔交易，手上持有股票的最大利润
# 初始化一个极小值，表示不可能状态
dp = [[[-10**9, -10**9] for _ in range(k+1)] for _ in range(n)]
# 第0天的基准状态
dp[0][0][0] = 0           # 第0天，没交易，不持有股票，利润为0
dp[0][0][1] = -prices[0] # 第0天，没交易但持有股票，说明买了，利润为-prices[0]
for i in range(1, n):
for j in range(k + 1):
# 状态转移方程：
# 1. 今天不持有股票：昨天也不持有（休息），或昨天持有今天卖出（完成一笔交易）
dp[i][j][0] = dp[i-1][j][0]  # 休息
if j > 0:
# 卖出操作会使交易次数计数，注意j是“最多j笔”，卖出时对应的是昨天的持有状态，交易计数是j-1到j
dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][1] + prices[i])
# 2. 今天持有股票：昨天也持有（休息），或昨天不持有今天买入
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
# 答案：最后一天，交易次数不超过k，不持有股票的最大值
return max(dp[n-1][j][0] for j in range(k+1))
# 测试用例
if __name__ == "__main__":
print(maxProfit(2, [3,2,6,5,0,3]))  # 输出: 7
# 解释：第2天买入(2)，第3天卖出(6)，利润4；第5天买入(0)，第6天卖出(3)，利润3；总利润7。

代码解析：我们定义了三维DP数组，第三维用0/1表示是否持有股票。状态转移清晰地刻画了所有操作： - dp[i][j][0]（不持有）可以从两个状态来：1) 昨天也不持有，今天休息；2) 昨天持有，今天卖出（此时交易计数增加，所以从 j-1 转移）。 - dp[i][j][1]（持有）可以从两个状态来：1) 昨天也持有，今天休息；2) 昨天不持有，今天买入（买入不增加交易计数，交易在卖出时结算）。 初始化需小心设置基准状态。最终答案取最后一天、任意交易次数、不持有股票的最大值。

对比分析

分析： - 背包问题的优化核心在于遍历顺序，这直接决定了物品的选择次数（一次或无限次）。 - 区间DP的模板化程度高，但时间复杂度常为O(n³)，适用于n较小（通常≤500）的场景。 - 状态机DP的思想最为通用，它将复杂的过程分解为清晰的状态和转移，是建模利器。股票问题中，交易次数 k 的维度处理是难点。

最佳实践

1. 先定义清晰的状态：动规解题的第一步，也是最关键的一步，是用一句自然语言明确说出 dp[i] 或 dp[i][j] 代表什么。例如：“dp[i][j] 表示用前 i 种硬币凑出金额 j 的组合数。” 模糊的状态定义必然导致错误的转移方程。

2. 画图辅助分析：对于区间DP和状态机DP，在纸上画出区间分割示意图或状态转移图。例如，画出 dp[i][j] 如何由 dp[i][k] 和 dp[k+1][j] 合并，或者画出“持有”、“不持有”状态之间的箭头。可视化能极大降低思维复杂度。

3. 从记忆化搜索入手：对于复杂的区间DP或树形DP，直接写递推可能很困难。可以先写一个带缓存的递归函数（记忆化搜索），其逻辑往往更直观。确保递归正确后，再根据递归的依赖关系转化为自底向上的递推DP，这能有效减少错误。

4. 注意空间优化的陷阱：使用一维数组进行空间优化时，务必确认内层循环的遍历方向。一个简单的口诀：“0-1背包逆序，完全背包正序，组合问题（不考虑顺序）先物品后容量，排列问题（考虑顺序）先容量后物品。” 在提交前，用一个小例子手动模拟一遍更新过程。

5. 利用问题特性进行剪枝：在背包问题中，如果物品重量很大，可以只遍历到 min(current_sum, target)；在区间DP中，如果某些区间无效，可以跳过；在股票问题中，当 k >= n//2 时退化为贪心。这些优化不仅能提升效率，有时也是解题的必要步骤。

小结

本节深入探讨了动态规划的三个高级范式：背包问题、区间DP和状态机DP。0-1背包与完全背包的核心区别在于物品的重复性，体现在代码上仅仅是遍历顺序的不同。区间DP通过固定模板——枚举长度、起点和分割点——解决了序列分割类问题。状态机DP则为我们提供了刻画多状态、多操作系统的清晰框架，是解决复杂流程问题的利器。

掌握这些进阶模型，意味着你已具备了解决LeetCode中大部分动态规划难题的能力。关键在于勤加练习，将状态定义、转移方程和优化技巧内化为直觉。记住，动态规划的本质是“聪明的暴力枚举”加上“记忆化”，其威力来自于对子问题重叠性的极致利用。

下一节：贪心算法：局部