区间DP
高级区间 DP 是 CSP-S 高频考点，经典问题：石子合并、矩阵链乘。
// 算法讲解
区间DP
演示区间DP求解石子合并问题的过程。
待机
速度 中
待机 ⌨1int intervalDP(vector<int>& a) {
2 int n = a.size();
3 vector<int> prefix(n + 1, 0);
4 for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + a[i];
5 vector<vector<int>> dp(n, vector<int>(n, 0));
6 for (int len = 2; len <= n; len++)
7 for (int i = 0; i + len - 1 < n; i++) {
8 int j = i + len - 1;
9 dp[i][j] = INT_MAX;
10 for (int k = i; k < j; k++)
11 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
12 dp[i][j] += prefix[j+1] - prefix[i];
13 }
14 return dp[0][n-1];
15}
复杂度分析
时间 O(n³)
空间 O(n²)
最优 O(n³)
最坏 O(n³)
算法讲解
区间 DP 在区间 [i,j] 上定义状态，转移时枚举分割点 k。
经典问题：石子合并（合并相邻两堆的最小代价）。
实现方式：按区间长度从小到大枚举，O(n³) 时间复杂度。
它属于"分治 + DP"的混合策略。