区间 DPCSP-S

💡 核心思想

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

🎯 直觉理解

想象你要把一堆石子合并成一堆。每次只能合并相邻的两堆，代价是两堆石子的重量之和。你要找到一个合并顺序使总代价最小。这就是"先解决小段，再合并成大段"的思路。

📝 算法流程

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 <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> 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<vector<int>> dp(n+1, vector<int>(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;
}

⚠️ 常见坑点

📚 相关题目