区间型DP入门

区间 DP

算法简介

• 时间复杂度：通常为 $O(n^3)$
• 基本枚举顺序：先枚举区间长度 $len$，再枚举左端点 $i$，最后枚举断点 $k$

---



一、代价合并模型





1. 核心原理



这是最基础的模型。问题通常描述为：将一些元素合并成一个大元素，每次合并产生一定的代价或收益。

• 状态转移：

$$ dp[i][j] = \max_{i \le k j} { dp[i][k] + dp[k+1][j] } + \text{cost}(i, j) $$

其中 $k$ 为区间 $[i, j]$ 的分割点。

---



2. 常用技巧



• 断环成链
处理环形问题（如项链、环形石子）时，将数组复制一份接在尾部：$a[1 \dots n] \rightarrow a[1 \dots 2n]$，
最后在长度为 $n$ 的区间中找最优解。


---



3. 代码模板





// 代价合并通用模板
for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;
}

for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;
        for (int k = i; k < j; k++) {
            dp[i][j] = min(
                dp[i][j],
                dp[i][k] + dp[k + 1][j] + cost(i, j)
            );
        }
    }
}



---


二、特征消除模型





1. 核心原理



这类问题利用区间端点的特征（如字符相等）来优化转移，常见于回文串、涂色、祖玛游戏等。

• 若 $a[i] = a[j]$，说明左右端点特征一致，区间 $[i, j]$ 可以直接由内部状态扩展而来（如 $dp[i+1][j-1]$），通常可以减少一次操作或降低代价。
• 若 $a[i] \ne a[j]$，说明左右端点无法直接合并，必须枚举断点 $k$ 将区间拆分。

---



2. 代码模板





// 特征消除 / 压缩类模板
for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;

        if (a[i] == a[j]) {
            dp[i][j] = ...; // 继承或压缩
        } else {
            dp[i][j] = INF;
        }

        for (int k = i; k < j; k++) {
            dp[i][j] = min(
                dp[i][j],
                dp[i][k] + dp[k + 1][j]
            );
        }
    }
}



---


三、状态扩展模型





1. 核心原理



当简单的 $dp[i][j]$ 无法完整描述当前局面时，需要增加维度。

• $dp[i][j][0]$：区间 $[i, j]$ 已处理完，最后停在左端点 $i$
• $dp[i][j][1]$：区间 $[i, j]$ 已处理完，最后停在右端点 $j$

2. 代码模板

// 0 / 1 端点状态模板
for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;

        dp[i][j][0] = min(
            dp[i + 1][j][0] + dist(i + 1, i),
            dp[i + 1][j][1] + dist(j, i)
        );

        dp[i][j][1] = min(
            dp[i][j - 1][0] + dist(i, j),
            dp[i][j - 1][1] + dist(j - 1, j)
        );
    }
}