区间 DPCSP-S

💡 核心思想

区间 DP 的状态定义在区间 $[l, r]$ 上，通过枚举区间内的分割点来合并子区间的结果。典型特征是"大区间的解由小区间的解合并得到"。经典问题：石子合并、矩阵链乘法。

🎯 直觉理解

区间 DP 是"小区间拼大区间"：先算好所有长度为 1 的区间，再算长度 2、3……大的区间由两个更小的区间合并而来。

经典例子石子合并：把 n 堆石子排成一圈，每次合并相邻两堆。$dp[l][r]$ 表示合并 $[l,r]$ 这段的最小代价，枚举最后一步在 k 处切开：$dp[l][r]=min(dp[l][k]+dp[k+1][r])+sum(l,r)$。

区间 DP 的套路：三层循环——外层枚举区间长度，中层枚举起点，内层枚举分割点 k。先写长度小的区间（长度从 1 开始），保证算大区间时小区间已经就绪。

📝 算法流程

1. 状态：$dp[l][r]$ = 区间 $[l,r]$ 的最优值
2. 转移：枚举分界点 $k$，合并左右两部分
3. 遍历：外层枚举区间长度 len，内层枚举左端点 l
4. 初始化：$dp[i][i] = $ 边界值

$$dp[l][r] = \min_{k=l}^{r-1} \{dp[l][k] + dp[k+1][r]\} + cost(l,r)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
int main() {
    int n; cin >> n;
    vector a(n+1), s(n+1, 0);
    for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }
    vector> dp(n+1, vector(n+1, 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] = INT_MAX;
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r] - s[l-1]);
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目