区间 DP

概念讲解

什么是区间 DP？

区间 DP 是在区间上进行的动态规划，通常用 $dp[i][j]$ 表示区间 $[i, j]$ 的最优解。

通用框架

12345678for (int len = 2; len <= n; len++) {         // 枚举区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 终点
        for (int k = i; k < j; k++) {        // 枚举分割点
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

经典问题

1. 石子合并

问题： n 堆石子，每次合并相邻两堆，代价为两堆之和，求最小总代价。

123456789101112131415161718int mergeStones(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n+1, 0);
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + stones[i-1];
    
    vector<vector<int>> dp(n+1, vector<int>(n+1, 1e9));
    for (int i = 1; i <= n; i++) dp[i][i] = 0;
    
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]);
            }
        }
    }
    return dp[1][n];
}

时间复杂度：$O(n^3)$

考点分析

初赛考查方式

1. 程序阅读： 区间 DP
2. 编程题： 区间问题

常见考点

• 石子合并
• 枚举顺序
• 环形处理

例题精讲

例题 1：石子合并

题目： 3 堆石子 {1, 2, 3}，求最小代价。

解答：

先合并 1+2=3，再合并 3+3=6，总代价 9。

练习题

1. 区间 DP 的枚举顺序是什么？

12345678for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        for (int k = i; k < j; k++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

2. 石子合并的时间复杂度是多少？

3. 环形问题怎么处理？

12345// 原数组：a[1..n]
// 新数组：a[1..2n]，其中 a[i+n] = a[i]
for (int i = 1; i <= n; i++) {
    a[i + n] = a[i];
}

易错点

⚠️ 注意：

1. 先枚举长度，再枚举起点
2. 分割点 k 要遍历所有可能
3. 环形问题可以破环成链
4. 初始化要正确