CSP-S 提高级 · CSP 2026 提高级第一轮 第 6 题

【单选】有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。

相邻两堆合并是区间 DP 的经典模型：dp[i][j] = 把 a[i..j] 合并成一堆的最小代价，转移为 dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i..j)。长度从 2 推到 5，逐层填表即可。

用贪心"每次合并最小的两堆"（那适用于"任意两堆可合并"的哈夫曼模型，本题只能合并相邻两堆，贪心会出错）；也容易漏加区间和 sum(i..j) 这一项。

解析

本题考查区间动态规划（相邻石子合并问题）。

状态与转移

设 dp[i][j] = 把第 i 堆到第 j 堆合并成一堆的最小总代价，sum(i, j) = a[i] + … + a[j]。

dp[i][j] = min{ dp[i][k] + dp[k+1][j] } + sum(i, j)（i ≤ k < j） dp[i][i] = 0

含义：先把 [i..k] 和 [k+1..j] 各自合并成一堆（代价 dp[i][k] + dp[k+1][j]），再合并这两堆（代价为本区间总重 sum(i,j)）。

逐层填表

数组 a = [4, 1, 3, 2, 5]，前缀和：s₀=0, s₁=4, s₂=5, s₃=8, s₄=10, s₅=15

长度 2（dp = 两数之和）

长度 3

• [1,3]：k=1 → 0+dp[2][3]=4；k=2 → dp[1][2]+0=5 → 取 4，加 sum(1,3)=8 → dp[1][3] = 12
• [2,4]：k=2 → 0+5=5；k=3 → 4+0=4 → 取 4，加 sum(2,4)=6 → dp[2][4] = 10
• [3,5]：k=3 → 0+7=7；k=4 → 5+0=5 → 取 5，加 sum(3,5)=10 → dp[3][5] = 15

长度 4

• [1,4]：k=1 → 0+10=10；k=2 → 5+5=10；k=3 → 12+0=12 → 取 10，加 sum(1,4)=10 → dp[1][4] = 20
• [2,5]：k=2 → 0+15=15；k=3 → 4+7=11；k=4 → 10+0=10 → 取 10，加 sum(2,5)=11 → dp[2][5] = 21

长度 5（答案）

• [1,5]：k=1 → 0+21=21；k=2 → 5+15=20；k=3 → 12+7=19；k=4 → 20+0=20 → 取 19，加 sum(1,5)=15 → dp[1][5] = 34

答案 C（34）。

最优合并顺序示例

k = 3 对应：先合并 [1..3]（4,1,3，代价 12）与 [4..5]（2,5，代价 7），最后合并两大堆（代价 15）→ 总计 12 + 7 + 15 = 34 ✓

其他选项为什么错

• A. 36、B. 35：非最优的合并顺序（如从两端往里合）得到的结果；
• D. 33：常来自"贪心取相邻最小对"（先合 1+3? 或 1+2）产生的偏小值，但相邻约束下不可达。

记忆点

• 判别关键："只能合并相邻两堆" → 区间 DP；"任意两堆可合并" → 哈夫曼/优先队列贪心，两者极易混淆；
• 区间 DP 的填写顺序必须按区间长度从小到大，因为长区间的转移依赖短区间；
• 复杂度 O(n³)，本题 n = 5 手算完全够用。