区间 dp 模型

区间 dp 的状态如何定义？

• 定义: 用区间左右端点作为状态维度的动态规划;
• 状态: dp[i][j] 表示区间 [i, j] 上的最优解、可行性或方案数;
• 阶段: 按区间长度从小到大划分, 长度更小的区间先算好;
• 结构: 大区间的解由长度更小的区间合并而来;

从中间向两侧的转移怎么写？

• 适用: 端点收缩型问题, 如回文判定;
• 方程: dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i][j-1]) + cost[i][j];
• 依赖方向: 需要下方 [i+1, j]、左方 [i, j-1]、左下方 [i+1, j-1];
• 遍历顺序: i 倒序, j 正序, 保证依赖项先计算;
• 边界: 先固定区间为空或单元素的情形, 再处理 i === j 的特例;

for i in range(size - 1, -1, -1):
    for j in range(i + 1, size):
        dp[i][j] = max(dp[i + 1][j - 1], dp[i + 1][j], dp[i][j - 1]) + cost[i][j]

多个区间合并的转移怎么写？

• 适用: 分割合并型问题, 如戳气球、矩阵连乘;
• 方程: dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + cost[i][j]), i <= k <= j;
• 依赖方向: 需要同一区间内更小的左右两段;
• 遍历顺序: 外层枚举区间长度, 内层枚举起点得到终点, 再枚举分割点 k;

for length in range(1, n + 1):
    for i in range(n):
        j = i + length - 1
        if j >= n:
            break
        dp[i][j] = float("-inf")
        for k in range(i + 1, j):
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + cost[i][j])

• 开闭区间: k 取开区间还是闭区间由题意决定, 必须与 cost 的定义保持一致;

区间 dp 的遍历顺序为什么特殊？

• 原因: 转移把区间拆成更短区间, 必须保证所有更短区间已经算完;
• 两种等价写法:
  • 按区间长度从小到大枚举 (最直观);
  • 按左端点倒序、右端点正序枚举 (依赖关系恰好满足);
• 复杂度: 长度为 n 的区间 dp 通常是时间 O(n^3) (枚举分割点) 或 O(n^2) (仅端点收缩), 空间 O(n^2);