🪨 石子堆
(等待开始)
📊 区间 DP 表 dp[i][j] (最小合并代价)
🧮 当前计算
(等待开始)
⭐ 当前最小代价
—
每次合并相邻两堆,代价是两堆之和。求全部合并成一堆的最小总代价。
先算小区间(2堆合并),再算大区间(3堆、4堆……)。大区间的答案由小区间拼出来。
合并区间 [i,j] 时,先合 [i,k] 再合 [k+1,j],最后把两堆并成一堆。试遍所有 k 取最小。
快速算区间 [i,j] 的石子总数:sum[i][j] = 前缀和[j+1] − 前缀和[i]。