区间 DP：区间分割合并型

一、区间 DP 简介

1. 从线性 DP 到区间 DP

在线性 DP 中，状态通常用一个下标表示。例如：

dp[i]=\text{处理到第 }i\text{ 个位置时的最优结果}

如果一个问题的子问题是一段连续区间，就需要同时记录左右端点：

dp[l][r]=\text{处理区间 }[l,r]\text{ 后的结果}

这类以区间左右端点作为状态的动态规划，称为区间 DP。

区间 DP 的核心仍然是：

定义状态；
根据最后一步或区间结构写转移；
按依赖关系确定计算顺序。

2. 区间 DP 解决什么问题

区间 DP 主要处理具有以下特征的问题：

对象按顺序排列；
子问题对应原序列中的一段连续区间；
大区间的答案可以由更短区间的答案得到；
操作通常涉及区间的合并、分割、端点选择或匹配。

区间 DP 常见于石子合并、表达式求值、括号匹配、字符串处理、区间博弈和一些区间计数问题。

二、区间分割合并型

1. 基本思想

这类问题的关键是观察一个区间的最后一次操作。

如果最后一步把区间 $[l,r]$ 合并成一个整体，那么在这一步之前，区间通常已经被分成两段：

[l, k] 和 [k + 1, r]

枚举分割点 $k$ ，就能枚举最后一步的所有可能情况。

常见转移形式为：

$$dp[l][r] = \operatorname{opt}_{l\le k<r} \left(dp[l][k]+dp[k+1][r]+cost(l,r,k)\right)$$

其中 cost 是最后一次合并产生的额外代价。

2. 为什么按区间长度计算

dp[l][r] 会依赖 dp[l][k] 和 dp[k+1][r]。这两个区间都比 [l,r] 短，因此要先求出短区间，再求长区间。

所以通常使用：

区间长度 1 → 区间长度 2 → … → 区间长度 n

代码框架为：

for (int len = 1; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;
        // 计算 dp[l][r]
    }
}

三、例题：线性石子合并

1. 题目

有 $n$ 堆石子排成一排，第 $i$ 堆有 $a_i$ 颗石子。每次只能合并相邻的两堆，合并代价等于两堆石子的总数。求把所有石子合并成一堆的最小总代价。

2. 状态定义

定义：

$$dp[l][r] = \text{将第 }l\text{ 堆到第 }r\text{ 堆合并成一堆的最小代价}$$

只有一堆石子时不需要合并：

dp[i][i]=0

3. 状态转移

考虑区间 $[l,r]$ 的最后一次合并。设最后一次合并的位置为 $k$ ，那么合并前的两堆分别来自：

[l, k] 和 [k + 1, r]

固定 $k$ 时，总代价为：

dp[l][k]+dp[k+1][r]+sum(l,r)

其中 sum(l,r) 是区间内所有石子的总数，也是最后合并两堆的代价。

枚举所有 $k$ ：

$$dp[l][r] = \min_{l\le k<r} \left(dp[l][k]+dp[k+1][r]+sum(l,r)\right)$$

4. 用前缀和求区间和

定义：

prefix[i]=a_1+a_2+\cdots+a_i

则：

sum(l,r)=prefix[r]-prefix[l-1]

这样每次求区间和只需要 $O(1)$ 时间，避免在转移中再次枚举区间。

5. C++ 实现

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1005;  // 若题目 n 更大，需按数据范围调整
long long prefix[MAXN];
long long dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    // 长度为 1 的区间 dp[i][i] = 0，已经完成初始化。
    // 先计算短区间，保证转移所需的子区间已经计算完成。
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = (1LL << 60);

            // k 是最后一次合并的分割点。
            for (int k = l; k < r; ++k) {
                long long intervalSum = prefix[r] - prefix[l - 1];

                dp[l][r] = min(
                    dp[l][r],
                    dp[l][k] + dp[k + 1][r] + intervalSum
                );
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

这里用全局二维数组保存 DP 状态。MAXN 要根据题目给出的最大 $n$ 设置；数组开多大必须覆盖所有合法下标。

6. 三层循环分别表示什么

for (int len = 2; len <= n; ++len)

枚举当前区间长度。长度越小的区间越早计算。

for (int l = 1; l + len - 1 <= n; ++l)

枚举当前长度下的左端点，右端点由 r = l + len - 1 得到。

for (int k = l; k < r; ++k)

枚举最后一次合并的位置，左区间为 [l,k]，右区间为 [k+1,r]。

7. 正确性与复杂度

对于长度为 1 的区间，dp[i][i] = 0，显然正确。

对于长度大于 1 的区间，最后一次合并必然存在一个分割点 $k$ 。当所有更短区间都已经求得最优值后，枚举所有 $k$ 并取最小值，就覆盖了所有合法的最后一次合并方式，因此得到当前区间的最优值。

共有 $O(n^2)$ 个区间，每个区间枚举 $O(n)$ 个分割点，所以：

时间复杂度： $O(n^3)$ ；
空间复杂度： $O(n^2)$ 。