动态规划之五——区间DP

背景

1. 城市各处分布有大小不同的垃圾收集点，而垃圾掩埋场一般都在城郊，为了效率，会用小垃圾车将各个垃圾收集点的垃圾多次运到不同的垃圾站，再用大车拖到掩埋场。这就涉及垃圾清运路线的设计：相邻垃圾收集点的垃圾需合并处理，算法可帮助设计最小清运成本的路线。

一、区间DP（Interval Dynamic Programming）

二、问题引入：石子合并

问题描述：
有 N 堆石子排成一列，每堆重量为 w[i]。每次合并相邻两堆，代价为两堆重量之和，最终合并为一堆。求最小总代价。
示例：
输入：N=4, w=[4, 5, 1, 2]
输出：34
解释：
合并顺序：

[4,5] → 代价 9，剩余 [9,1,2]
[1,2] → 代价 3，剩余 [9,3]
[9,3] → 代价 12，总代价 9+3+12=24（实际最优解可能不同，需动态规划求解）。

三、模拟法分析

四、动态规划分析

1. 状态定义

dp[i][j]：合并第 i 到第 j 堆石子的最小代价。
前缀和优化：定义 s[i] 为前 i 堆石子重量和，方便计算区间和。

2. 状态转移方程

枚举分割点 k（i ≤ k < j），将区间 [i,j] 拆分为 [i,k] 和 [k+1,j]。
合并代价为 s[j] - s[i-1]（区间 [i,j] 的总重量）。

转移方程：

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (s[j] - s[i-1])  
（对所有 k 取最小值）

3. 边界条件

dp[i][i] = 0（单堆无需合并）。
填表顺序：按区间长度从小到大枚举（从长度为2开始）。

4. 填表示例

以 w=[4,5,1,2] 为例（前缀和 s=[0,4,9,10,12]）：

区间长度	计算 `dp[i][j]` 的过程	结果
长度=2	`dp[1][2] = 4+5 = 9`	9
	`dp[2][3] = 5+1 = 6`	6
	`dp[3][4] = 1+2 = 3`	3
长度=3	`dp[1][3] = min(dp[1][1]+dp[2][3], dp[1][2]+dp[3][3}) + 10 = min(0+6, 9+0) + 10 = 16`	16
长度=4	`dp[1][4]` 枚举 `k=1,2,3`，取最小值后加 `s[4]=12`	最终结果

四、代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> w(n+1), s(n+1, 0);
    for (int i=1; i<=n; i++) {
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }
    
    vector<vector<int> > dp(n+1, vector<int>(n+1, 0));
    for (int len=2; len<=n; len++) {          // 枚举区间长度
        for (int i=1; i+len-1<=n; i++) {     // 枚举起点i
            int j = i + len - 1;             // 终点j
            dp[i][j] = INT_MAX;
            for (int k=i; k<j; k++) {        // 枚举分割点k
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    cout << dp[1][n];
    return 0;
}

关键点解释：

三重循环顺序：长度 → 起点 → 分割点。
时间复杂度：O(n³)，适用于 n ≤ 300。
空间优化：若 n 较大，可使用滚动数组优化（但对多数竞赛题无需）。

五、常见题型与变种

经典问题
- 最长回文子序列：dp[i][j] 表示 s[i..j] 的最长回文子序列长度。
```
if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
```
- 括号匹配：dp[i][j] 表示 s[i..j] 的最长合法括号子串长度。
变种问题
- 环形石子合并：将石子排列成环，需破环成链（复制数组处理）。
- 二维区间DP：如棋盘分割、矩阵链乘法等。

六、常见错误与技巧

错误点
- 区间枚举顺序错误：未按长度从小到大处理。
- 遗漏分割点计算：未遍历所有可能的 k。
- 未处理前缀和：直接累加 w[i] 导致重复计算。
优化技巧
- 四边形不等式优化：将时间复杂度降至 O(n²)（需满足决策单调性）。
- 记忆化搜索：适用于不确定填表顺序的复杂区间DP。

扩展练习：

*学习笔记

暂没有学习笔记，快来抢first blood ！

背景​

一、区间DP（Interval Dynamic Programming）​

二、问题引入：石子合并​

三、模拟法分析​

四、动态规划分析​

1. 状态定义​

2. 状态转移方程​

3. 边界条件​

4. 填表示例​

四、代码实现​

五、常见题型与变种​

六、常见错误与技巧​

扩展练习：​

*学习笔记​

背景