数据结构与算法 / 系统课时

用区间状态解决合并型问题

用区间状态解决合并型问题

合并型动态规划的难点,是一次操作会把大区间拆成更小区间,并且不同切分顺序会影响总收益。本篇用“区间状态 + 枚举最后一次操作”建立统一套路,并用戳气球写出可运行实现。

学习目标

  • 能用 dp[left][right] 表示一个区间内的最优值
  • 能通过枚举切分点或最后一次操作写出状态转移
  • 能判断区间 DP 的遍历顺序、边界和复杂度

先把状态定义成一个闭合子问题

区间 DP 适合“答案由一段连续范围决定”的问题。关键不是先写循环,而是让一个状态只依赖更短的区间。以戳气球为例,在数组两端补上虚拟气球 1,定义 dp[left][right] 为开区间 (left, right) 内气球全部戳完能获得的最大金币。

之所以使用开区间,是因为当区间里只剩最后一个气球 k 时,它左右仍保留边界 left 和 right。此时最后一次操作的收益可以稳定写成 nums[left] * nums[k] * nums[right],不会再受区间内部其他气球影响。

区间 DP 的最后一次切分

枚举最后一次操作得到转移

假设 k 是 (left, right) 中最后被戳的气球。那在它之前,左侧 (left, k) 与右侧 (k, right) 已经分别处理完,所以当前候选答案是:

dp[left][k]+nums[left]×nums[k]×nums[right]+dp[k][right]dp[left][k] + nums[left] \times nums[k] \times nums[right] + dp[k][right]

对所有 left < k < right 取最大值即可。因为大区间依赖两个更短区间,所以遍历时必须先算短区间,再算长区间。最直接的写法是让区间长度从小到大增长。

用戳气球跑通模板

下面的程序完整实现 LeetCode 312 的区间 DP,并输出样例答案。

python
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]))

预期输出:

text
167

这里最重要的不是记住三层循环,而是认清三层循环分别对应“区间长度、左边界、最后一次操作位置”。只要状态定义和最后一次操作成立,循环顺序就能自然推出。

识别同类问题的切分方式

矩阵链乘法、区间合并、最优括号化等题目也常出现同一结构:dp[left][right] 表示一段区间的最优值,再枚举一个切分点 k,把原问题组合为左区间、右区间和跨越切分点的代价。

需要特别检查两个边界。第一,状态表示的是闭区间还是开区间,不能在转移时混用。第二,切分点必须保证依赖的子区间已经计算完成,否则即使公式正确,也会读取尚未更新的状态。

对长度为 n 的数组,典型区间 DP 有 O(n2)O(n^2) 个状态,每个状态枚举 O(n)O(n) 个切分点,因此时间复杂度通常是 O(n3)O(n^3),空间复杂度是 O(n2)O(n^2)。遇到“连续区间 + 枚举切分点 + 合并两侧答案”的题目时,可以优先尝试这套建模。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用区间状态解决合并型问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通