数据结构与算法 / 系统课时
用区间状态解决合并型问题
用区间状态解决合并型问题
合并型动态规划的难点,是一次操作会把大区间拆成更小区间,并且不同切分顺序会影响总收益。本篇用“区间状态 + 枚举最后一次操作”建立统一套路,并用戳气球写出可运行实现。
学习目标
- 能用
dp[left][right]表示一个区间内的最优值 - 能通过枚举切分点或最后一次操作写出状态转移
- 能判断区间 DP 的遍历顺序、边界和复杂度
先把状态定义成一个闭合子问题
区间 DP 适合“答案由一段连续范围决定”的问题。关键不是先写循环,而是让一个状态只依赖更短的区间。以戳气球为例,在数组两端补上虚拟气球 1,定义 dp[left][right] 为开区间 (left, right) 内气球全部戳完能获得的最大金币。
之所以使用开区间,是因为当区间里只剩最后一个气球 k 时,它左右仍保留边界 left 和 right。此时最后一次操作的收益可以稳定写成 nums[left] * nums[k] * nums[right],不会再受区间内部其他气球影响。

枚举最后一次操作得到转移
假设 k 是 (left, right) 中最后被戳的气球。那在它之前,左侧 (left, k) 与右侧 (k, right) 已经分别处理完,所以当前候选答案是:
对所有 left < k < right 取最大值即可。因为大区间依赖两个更短区间,所以遍历时必须先算短区间,再算长区间。最直接的写法是让区间长度从小到大增长。
用戳气球跑通模板
下面的程序完整实现 LeetCode 312 的区间 DP,并输出样例答案。
def max_coins(nums):
values = [1] + nums + [1]
n = len(values)
dp = [[0] * n for _ in range(n)]
# gap 是左右边界的距离;小区间必须先于大区间计算。
for gap in range(2, n):
for left in range(0, n - gap):
right = left + gap
for k in range(left + 1, right):
coins = (
dp[left][k]
+ values[left] * values[k] * values[right]
+ dp[k][right]
)
dp[left][right] = max(dp[left][right], coins)
return dp[0][n - 1]
if __name__ == "__main__":
print(max_coins([3, 1, 5, 8]))预期输出:
167这里最重要的不是记住三层循环,而是认清三层循环分别对应“区间长度、左边界、最后一次操作位置”。只要状态定义和最后一次操作成立,循环顺序就能自然推出。
识别同类问题的切分方式
矩阵链乘法、区间合并、最优括号化等题目也常出现同一结构:dp[left][right] 表示一段区间的最优值,再枚举一个切分点 k,把原问题组合为左区间、右区间和跨越切分点的代价。
需要特别检查两个边界。第一,状态表示的是闭区间还是开区间,不能在转移时混用。第二,切分点必须保证依赖的子区间已经计算完成,否则即使公式正确,也会读取尚未更新的状态。
对长度为 n 的数组,典型区间 DP 有 个状态,每个状态枚举 个切分点,因此时间复杂度通常是 ,空间复杂度是 。遇到“连续区间 + 枚举切分点 + 合并两侧答案”的题目时,可以优先尝试这套建模。