一、课上练习

编程练习

1. 合并石子：L3481

二、知识总结

✨ 核心思想

合并石子问题是区间动态规划的经典问题。

问题描述：

• 有一行石子堆，每堆石子有一定的数量
• 每次可以合并相邻的两堆石子，合并的成本为两堆石子的数量之和
• 目标是合并所有石子堆，使得整个合并过程的总成本最小

✨ 动态规划解法

状态定义

定义 dp[i][j] 为将第 i 堆到第 j 堆石子合并成一堆的最小成本。同时使用前缀和数组 prefix 来快速计算区间和。

状态转移方程

dp[i][j] 的值通过枚举分割点 k（其中 i <= k < j）来确定：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1])

其中 prefix[j] - prefix[i-1] 表示第 i 堆到第 j 堆石子的总数量，即最后一次合并的成本。

初始化

对于任何 i，dp[i][i] = 0，因为单个石子堆不需要合并。

计算顺序

按照区间长度从小到大的顺序计算：先计算所有长度为 2 的区间，再计算长度为 3 的区间，依次类推，直到整个区间。

1#include <iostream>
2#include <vector>
3#include <climits>
4using namespace std;
5
6int mergeStones(vector<int>& stones) {
7    int n = stones.size();
8    vector<vector<int>> dp(n, vector<int>(n, 0));
9    vector<int> prefix(n + 1, 0);
10
11    for (int i = 0; i < n; i++) {
12        prefix[i + 1] = prefix[i] + stones[i];
13    }
14
15    for (int len = 2; len <= n; len++) {  // 控制区间长度
16        for (int i = 0; i <= n - len; i++) {
17            int j = i + len - 1;
18            dp[i][j] = INT_MAX;
19            for (int k = i; k < j; k++) {
20                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i]);
21            }
22        }
23    }
24
25    return dp[0][n - 1];
26}
27
28int main() {
29    vector<int> stones = {3, 5, 1, 2, 6};
30    cout << "Minimum cost to merge all stones: " << mergeStones(stones) << endl;
31    return 0;
32}

✨ 执行示例

以石子堆 stones = [3, 5, 1, 2] 为例，追踪区间 DP 的填充过程：

前缀和： prefix = [0, 3, 8, 9, 11]

区间 [i, j] 的石子总数 = prefix[j+1] - prefix[i]

初始化： dp[i][i] = 0（单堆不需要合并）

长度 len = 2（两堆合并）：

长度 len = 3（三堆合并）：

dp[0][2]（合并 [3, 5, 1]，总和=9）：

• k=0: dp[0][0]+dp[1][2]+9 = 0+6+9 = 15（先合并 [5,1]，再合并）
• k=1: dp[0][1]+dp[2][2]+9 = 8+0+9 = 17（先合并 [3,5]，再合并）
• dp[0][2] = min(15, 17) = 15

dp[1][3]（合并 [5, 1, 2]，总和=8）：

• k=1: dp[1][1]+dp[2][3]+8 = 0+3+8 = 11
• k=2: dp[1][2]+dp[3][3]+8 = 6+0+8 = 14
• dp[1][3] = min(11, 14) = 11

长度 len = 4（四堆合并）：

dp[0][3]（合并 [3, 5, 1, 2]，总和=11）：

• k=0: dp[0][0]+dp[1][3]+11 = 0+11+11 = 22
• k=1: dp[0][1]+dp[2][3]+11 = 8+3+11 = 22
• k=2: dp[0][2]+dp[3][3]+11 = 15+0+11 = 26
• dp[0][3] = min(22, 22, 26) = 22

最终答案：dp[0][3] = 22

✨ 解题步骤详解

解决区间 DP 问题的步骤：

1. 识别问题特征：问题涉及"相邻元素的合并"或"区间上的操作"
2. 计算前缀和：用于快速计算任意区间的元素总和
3. 按区间长度从小到大枚举：先算短区间，再算长区间
4. 枚举分割点：对每个区间 [i, j]，尝试所有分割点 k（i <= k < j）
5. 取最优分割：dp[i][j] = min(dp[i][k] + dp[k+1][j] + 区间和)

区间 DP 的通用模板：

1// 枚举区间长度
2for (int len = 2; len <= n; len++) {
3    // 枚举起点
4    for (int i = 0; i <= n - len; i++) {
5        int j = i + len - 1;  // 终点
6        dp[i][j] = INT_MAX;
7        // 枚举分割点
8        for (int k = i; k < j; k++) {
9            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, j));
10        }
11    }
12}

✨ 常见错误

1. 区间长度从 1 开始枚举：长度为 1 时 dp[i][i]=0 已经在初始化阶段完成，循环应从 len=2 开始
2. 分割点 k 的范围错误：k 的范围是 [i, j-1]，不是 [i, j]，否则 dp[k+1][j] 中 k+1 > j 导致越界
3. 前缀和下标偏移：区间 [i, j] 的和应为 prefix[j+1] - prefix[i]（使用 0-indexed 时），注意不要搞混
4. dp 数组没有正确初始化为 INT_MAX：在求最小值时，dp[i][j] 的初始值必须足够大
5. 混淆区间 DP 和线性 DP：区间 DP 需要三层循环（长度、起点、分割点），不能用简单的两层循环

✨ 算法评价

• 时间复杂度：O(n³)，三层循环（区间长度、起点、分割点）
• 空间复杂度：O(n²)，用于存储 dp 数组

✨ 应用场景

合并石子问题不仅是一个有趣的算法问题，它还可以应用于文件合并、数据压缩和资源优化等领域。它提供了一个通用框架，用于解决需要最小化连续分段合并成本的问题。

三、课后练习

编程练习

1. 乘积最大：L3482