线性动态规划：最小成本合并石子问题（进阶版——环形石子堆）
字数 2535 2025-12-09 22:48:29

线性动态规划：最小成本合并石子问题（进阶版——环形石子堆）

题目描述

有 n 堆石子排成一个环形，其中第 i 堆石子的数量为 stones[i]。你的任务是将所有石子合并成一堆，但每次只能合并相邻的两堆石子，合并的成本等于这两堆石子的数量之和。合并后，这两堆石子形成新的一堆，其数量为原来两堆之和，并占据原来的位置。合并的总成本是每次合并成本的总和。

你需要计算将 n 堆环形石子合并成一堆的最小总成本。

示例：

  • 输入：stones = [3, 4, 5, 1, 2]
  • 解释：这是一个环形排列，即 stones[0] 与 stones[4] 相邻。
  • 输出：34
  • 一种最优合并方式（成本计算略）可得最小总成本 34。

约束：

  • n == stones.length
  • 1 <= n <= 100
  • 1 <= stones[i] <= 1000

解题思路

这个问题本质上是经典的“合并石子”动态规划问题，但增加了“环形”条件。我们分两步解决：

  1. 解决线性版本：假设石子是线性排列（非环形）时，如何计算最小合并成本。
  2. 处理环形条件：将环形问题转化为线性问题求解。

步骤 1：线性版本（基础动态规划）

问题定义：

  • 给定数组 a[1..n] 表示 n 堆石子的数量（线性排列）。
  • 定义 dp[i][j] 为合并第 i 堆到第 j 堆石子（闭区间）为一堆的最小成本。
  • 目标是计算 dp[1][n]。

关键观察：

  • 合并 [i, j] 区间时，最后一步一定是将 [i, k] 和 [k+1, j] 这两大堆合并，其中 i ≤ k < j。
  • 合并最后一步的成本等于 [i, j] 区间内所有石子总和（因为合并的是两大堆的总和）。
  • 因此，状态转移方程为：

\[ dp[i][j] = \min_{k = i}^{j-1} \{ dp[i][k] + dp[k+1][j] \} + \text{sum}(i, j) \]

其中 sum(i, j) 是 a[i] + a[i+1] + ... + a[j]。

  • 初始化：dp[i][i] = 0（单堆无需合并）。

计算顺序：

  • 按区间长度 len 从小到大计算：len = 2 到 n。
  • 对于每个 len，枚举起点 i，计算 j = i + len - 1。

前缀和优化：

  • 预先计算前缀和数组 prefix，使得 sum(i, j) = prefix[j] - prefix[i-1]。

复杂度：状态数 O(n²)，每个状态转移 O(n)，总 O(n³)。

步骤 2：处理环形条件

环形意味着第 1 堆和第 n 堆相邻，合并时可能跨越环形边界。

核心技巧：破环成链

  • 将原数组复制一份接在后面：构造新数组 b，长度为 2n，其中 b[i] = stones[i % n]（0-index 转 1-index 需小心）。
  • 例如，stones = [3, 4, 5, 1, 2] 变成：

\[ b = [3, 4, 5, 1, 2, 3, 4, 5, 1, 2] \]

  • 现在，原环形问题中任意一种合并方式，都对应 b 中某个长度为 n 的连续子数组的线性合并。
  • 因此，我们只需在 b 上对所有长度为 n 的连续子数组应用线性动态规划，取最小值即可。

具体步骤：

  1. 构造 b 数组（长度 2n）。
  2. 计算 b 的前缀和。
  3. 在 b 上运行线性合并石子的 DP，但注意：
    • 我们只关心长度恰好为 n 的区间的最小合并成本。
    • 即计算 dp[i][i+n-1] 对于 i = 1 到 n 的最小值。

步骤 3：动态规划实现细节

以下以 1-index 为例（便于前缀和计算）。

初始化：

  • dp[i][i] = 0。
  • 前缀和 prefix[0] = 0，prefix[i] = prefix[i-1] + b[i]（i 从 1 到 2n）。

状态转移：

  • 对于长度 len = 2 到 n（因为环形中我们只需求到长度 n）：
    • 对于起点 i = 1 到 2n - len + 1：
      • j = i + len - 1。
      • dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (prefix[j] - prefix[i-1])，其中 k 从 i 到 j-1。

最终答案：

  • 在所有 i 中取 dp[i][i+n-1] 的最小值（i 从 1 到 n）。

步骤 4：复杂度优化说明

  • 直接实现的时间复杂度为 O(n³)，在 n ≤ 100 时可行（100³ = 1e6 操作量级）。
  • 如果 n 更大（例如 1000），可用四边形不等式优化到 O(n²)，但本题无需。

步骤 5：示例计算（简略演示）

以 stones = [3, 4, 5, 1, 2] 为例：

  1. 构造 b = [3, 4, 5, 1, 2, 3, 4, 5, 1, 2]（1-index：索引 1~10）。
  2. 计算前缀和（略）。
  3. 计算线性 DP 对所有区间 [i, j]（长度 ≤5）。
  4. 取所有长度为 5 的区间最小成本：
    • dp[1][5]：对应原始线性排列 [3,4,5,1,2] 的最小成本。
    • dp[2][6]：对应环形从第 2 堆开始的排列 [4,5,1,2,3]。
    • 等等。
  5. 最终发现最小值为 34。

总结

本题通过破环成链技巧，将环形问题转化为多个线性问题求解。线性部分使用经典的区间动态规划，定义 dp[i][j] 为合并区间 [i, j] 的最小成本，通过枚举最后一次合并的分界点进行状态转移。
关键点：

  1. 环形复制数组使长度变为 2n。
  2. 在复制数组上计算所有长度为 n 的区间的最小合并成本。
  3. 利用前缀和快速计算区间和，降低时间复杂度。

此方法可推广到其他环形区间 DP 问题，如环形能量项链、环形多边形剖分等。

线性动态规划：最小成本合并石子问题（进阶版——环形石子堆） 题目描述 有 n 堆石子排成一个环形，其中第 i 堆石子的数量为 stones[i] 。你的任务是将所有石子合并成一堆，但每次只能合并 相邻 的两堆石子，合并的 成本 等于这两堆石子的数量之和。合并后，这两堆石子形成新的一堆，其数量为原来两堆之和，并占据原来的位置。合并的总成本是每次合并成本的总和。 你需要计算将 n 堆环形石子合并成一堆的 最小总成本 。 示例 ： 输入： stones = [3, 4, 5, 1, 2] 解释：这是一个环形排列，即 stones[0] 与 stones[4] 相邻。 输出： 34 一种最优合并方式（成本计算略）可得最小总成本 34。 约束 ： n == stones.length 1 <= n <= 100 1 <= stones[i] <= 1000 解题思路 这个问题本质上是经典的“合并石子”动态规划问题，但增加了“环形”条件。我们分两步解决： 解决线性版本 ：假设石子是线性排列（非环形）时，如何计算最小合并成本。 处理环形条件 ：将环形问题转化为线性问题求解。 步骤 1：线性版本（基础动态规划） 问题定义 ： 给定数组 a[1..n] 表示 n 堆石子的数量（线性排列）。 定义 dp[i][j] 为合并第 i 堆到第 j 堆石子（闭区间）为 一堆 的最小成本。 目标是计算 dp[1][n] 。 关键观察 ： 合并 [i, j] 区间时，最后一步一定是将 [i, k] 和 [k+1, j] 这两大堆合并，其中 i ≤ k < j 。 合并最后一步的成本等于 [i, j] 区间内所有石子总和（因为合并的是两大堆的总和）。 因此，状态转移方程为： \[ dp[ i][ j] = \min_ {k = i}^{j-1} \{ dp[ i][ k] + dp[ k+1][ j ] \} + \text{sum}(i, j) \] 其中 sum(i, j) 是 a[i] + a[i+1] + ... + a[j] 。 初始化： dp[i][i] = 0 （单堆无需合并）。 计算顺序 ： 按区间长度 len 从小到大计算： len = 2 到 n 。 对于每个 len ，枚举起点 i ，计算 j = i + len - 1 。 前缀和优化 ： 预先计算前缀和数组 prefix ，使得 sum(i, j) = prefix[j] - prefix[i-1] 。 复杂度 ：状态数 O(n²)，每个状态转移 O(n)，总 O(n³)。 步骤 2：处理环形条件 环形意味着第 1 堆和第 n 堆相邻，合并时可能跨越环形边界。 核心技巧：破环成链 将原数组复制一份接在后面：构造新数组 b ，长度为 2n ，其中 b[i] = stones[i % n] （0-index 转 1-index 需小心）。 例如， stones = [3, 4, 5, 1, 2] 变成： \[ b = [ 3, 4, 5, 1, 2, 3, 4, 5, 1, 2 ] \] 现在，原环形问题中任意一种合并方式，都对应 b 中某个长度为 n 的连续子数组的线性合并。 因此，我们只需在 b 上对 所有长度为 n 的连续子数组 应用线性动态规划，取最小值即可。 具体步骤 ： 构造 b 数组（长度 2n ）。 计算 b 的前缀和。 在 b 上运行线性合并石子的 DP，但注意： 我们只关心长度恰好为 n 的区间的最小合并成本。 即计算 dp[i][i+n-1] 对于 i = 1 到 n 的最小值。 步骤 3：动态规划实现细节 以下以 1-index 为例（便于前缀和计算）。 初始化 ： dp[i][i] = 0 。 前缀和 prefix[0] = 0 ， prefix[i] = prefix[i-1] + b[i] （ i 从 1 到 2n ）。 状态转移 ： 对于长度 len = 2 到 n （因为环形中我们只需求到长度 n ）： 对于起点 i = 1 到 2n - len + 1 ： j = i + len - 1 。 dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (prefix[j] - prefix[i-1]) ，其中 k 从 i 到 j-1 。 最终答案 ： 在所有 i 中取 dp[i][i+n-1] 的最小值（ i 从 1 到 n ）。 步骤 4：复杂度优化说明 直接实现的时间复杂度为 O(n³)，在 n ≤ 100 时可行（100³ = 1e6 操作量级）。 如果 n 更大（例如 1000），可用 四边形不等式优化 到 O(n²)，但本题无需。 步骤 5：示例计算（简略演示） 以 stones = [3, 4, 5, 1, 2] 为例： 构造 b = [3, 4, 5, 1, 2, 3, 4, 5, 1, 2] （1-index：索引 1~10）。 计算前缀和（略）。 计算线性 DP 对所有区间 [i, j] （长度 ≤5）。 取所有长度为 5 的区间最小成本： dp[1][5] ：对应原始线性排列 [3,4,5,1,2] 的最小成本。 dp[2][6] ：对应环形从第 2 堆开始的排列 [4,5,1,2,3] 。 等等。 最终发现最小值为 34。 总结 本题通过 破环成链 技巧，将环形问题转化为多个线性问题求解。线性部分使用经典的区间动态规划，定义 dp[i][j] 为合并区间 [i, j] 的最小成本，通过枚举最后一次合并的分界点进行状态转移。 关键点： 环形复制数组使长度变为 2n 。 在复制数组上计算所有长度为 n 的区间的最小合并成本。 利用前缀和快速计算区间和，降低时间复杂度。 此方法可推广到其他环形区间 DP 问题，如环形能量项链、环形多边形剖分等。