环形石子合并的最小得分问题
字数 2456 2025-11-08 20:56:04

环形石子合并的最小得分问题

题目描述

有N堆石子排成一个环形，每堆石子的数量用一个数组stones表示，其中stones[i]表示第i堆石子的数量。环形意味着第1堆石子的下一堆是第2堆，...，第N-1堆的下一堆是第N堆，第N堆的下一堆是第1堆。

每次操作可以选择相邻的两堆石子合并成一堆，每次合并的代价是这两堆石子的数量之和。请编写一个程序，计算出将所有石子合并成一堆的最小总代价。

解题过程

  1. 问题分析

    • 这是一个经典的区间动态规划问题，但增加了“环形”条件。
    • 关键点在于，环形结构意味着合并操作可以从环上的任意位置开始。例如，对于环形石子序列[A, B, C, D]，可能的合并顺序包括A-B-C-D，B-C-D-A，C-D-A-B，D-A-B-C。
    • 我们的目标是找到所有可能的线性合并序列中，总代价最小的那一个。

  2. 解决环形问题的技巧：破环成链

    • 一个常见的技巧是将环断开，并复制一份接在末尾，从而将一个环形问题转化为一个长度为2N的线性问题。
    • 具体做法是：构造一个新数组newStones，长度为2 * N，其中newStones[i] = stones[i % N] (i 从0到2N-1)。
    • 例如，对于环形石子序列[1, 3, 2, 4]（N=4），我们构造的新数组为[1, 3, 2, 4, 1, 3, 2, 4]。
    • 这样，原环形问题中所有可能的合并起点（长度为N的区间），都对应了新线性数组中某个长度为N的连续子数组。我们只需要在这个长度为2N的线性数组上，求解所有长度为N的区间的最小合并代价，然后取最小值即可。

  3. 线性石子合并问题的动态规划思路

    • 我们定义动态规划状态：
      • dp[i][j] 表示将第i堆到第j堆石子（包含i和j）合并成一堆所需的最小代价。
    • 我们需要一个前缀和数组prefixSum来快速计算区间内石子的总和（即合并代价）。
      • prefixSum[k] 表示数组newStones从第0堆到第k-1堆的石子总数（通常前缀和数组这样定义便于计算区间和，prefixSum[j+1] - prefixSum[i]即为i到j的和）。
    • 状态转移方程：
      • 考虑最后一次合并操作。在合并第i堆到第j堆石子时，最后一步一定是将[i, k]和[k+1, j]这两大堆合并（其中k是介于i和j-1之间的一个位置）。
      • 合并[i, k]的代价是dp[i][k]，合并[k+1, j]的代价是dp[k+1][j]。
      • 最后将这两堆合并的代价是[i, j]区间内所有石子的总和，即prefixSum[j+1] - prefixSum[i]。
      • 因此，总的代价是这三部分之和。我们需要枚举所有可能的分割点k，找到使得总代价最小的那个。
      • 状态转移方程为：
        dp[i][j] = min( dp[i][k] + dp[k+1][j] + (prefixSum[j+1] - prefixSum[i]) )，对于所有满足 i <= k < j 的k。
    • 边界条件：
      • 当i == j时，只有一堆石子，不需要合并，代价为0。即dp[i][i] = 0。

  4. 计算顺序

    • 由于计算dp[i][j]时需要知道所有更短区间的结果（即dp[i][k]和dp[k+1][j]），我们应该按照区间长度len从小到大的顺序进行计算。
    • 先计算所有长度为1的区间（即单堆石子，dp[i][i]），然后计算长度为2的区间，接着是长度为3的区间，...，直到长度为N的区间。

  5. 算法步骤（针对环形问题）

    1. 如果石子堆数N为0，返回0。如果N为1，返回0（因为只有一堆）。
    2. 构造一个长度为2*N的新数组newStones，将原stones数组复制两份连接起来。
    3. 计算新数组的前缀和数组prefixSum，长度为2*N + 1。prefixSum[0] = 0, prefixSum[i] = newStones[0] + newStones[1] + ... + newStones[i-1]。
    4. 初始化一个大小为(2*N) x (2*N)的二维DP数组dp，初始值可以设为一个很大的数（比如INT_MAX）。
    5. 初始化边界条件：对于所有i从0到2*N-1，设置dp[i][i] = 0。
    6. 枚举区间长度len，从2到N（因为我们需要的是合并成一堆，即长度为N的区间，但我们需要计算所有小于等于N的区间来递推）：
      • 枚举区间起点i，从0到2*N - len：
        • 区间终点j = i + len - 1。
        • 枚举分割点k，从i到j-1：
          • cost = dp[i][k] + dp[k+1][j] + (prefixSum[j+1] - prefixSum[i])
          • 如果cost < dp[i][j]，则更新dp[i][j] = cost。
    7. 遍历所有可能的起点i（从0到N-1），对应的区间是[i, i+N-1]，找出最小的dp[i][i+N-1]，这个值就是环形石子合并的最小总代价。

  6. 复杂度分析

    • 时间复杂度：O(N³)。我们需要三重循环：外层循环区间长度O(N)，中层循环起点O(N)，内层循环分割点O(N)。由于我们处理的是长度为2N的数组，但区间长度只枚举到N，所以是O(N * N * N) = O(N³)。
    • 空间复杂度：O(N²)。主要用于存储DP表，大小为(2N) * (2N) ≈ 4N²，即O(N²)。

总结

通过“破环成链”的技巧，我们将环形石子合并问题转化为了一个在扩展线性数组上的区间动态规划问题。核心是定义状态dp[i][j]为合并区间[i, j]的最小代价，并通过枚举最后一次合并的分割点来建立状态转移关系。最后，在所有可能的长度为N的区间中寻找最小值，即为原环形问题的最优解。

环形石子合并的最小得分问题 题目描述 有N堆石子排成一个环形，每堆石子的数量用一个数组stones表示，其中stones[ i ]表示第i堆石子的数量。环形意味着第1堆石子的下一堆是第2堆，...，第N-1堆的下一堆是第N堆，第N堆的下一堆是第1堆。 每次操作可以选择相邻的两堆石子合并成一堆，每次合并的代价是这两堆石子的数量之和。请编写一个程序，计算出将所有石子合并成一堆的最小总代价。 解题过程 问题分析 这是一个经典的区间动态规划问题，但增加了“环形”条件。 关键点在于，环形结构意味着合并操作可以从环上的任意位置开始。例如，对于环形石子序列[ A, B, C, D ]，可能的合并顺序包括A-B-C-D，B-C-D-A，C-D-A-B，D-A-B-C。 我们的目标是找到所有可能的线性合并序列中，总代价最小的那一个。 解决环形问题的技巧：破环成链 一个常见的技巧是将环断开，并复制一份接在末尾，从而将一个环形问题转化为一个长度为2N的线性问题。 具体做法是：构造一个新数组 newStones ，长度为 2 * N ，其中 newStones[i] = stones[i % N] (i 从0到2N-1)。 例如，对于环形石子序列[ 1, 3, 2, 4]（N=4），我们构造的新数组为[ 1, 3, 2, 4, 1, 3, 2, 4 ]。 这样，原环形问题中所有可能的合并起点（长度为N的区间），都对应了新线性数组中某个长度为N的连续子数组。我们只需要在这个长度为2N的线性数组上，求解所有长度为N的区间的最小合并代价，然后取最小值即可。 线性石子合并问题的动态规划思路 我们定义动态规划状态： dp[i][j] 表示将第 i 堆到第 j 堆石子（包含i和j）合并成一堆所需的最小代价。 我们需要一个前缀和数组 prefixSum 来快速计算区间内石子的总和（即合并代价）。 prefixSum[k] 表示数组 newStones 从第0堆到第k-1堆的石子总数（通常前缀和数组这样定义便于计算区间和， prefixSum[j+1] - prefixSum[i] 即为i到j的和）。 状态转移方程 ： 考虑最后一次合并操作。在合并第i堆到第j堆石子时，最后一步一定是将 [i, k] 和 [k+1, j] 这两大堆合并（其中 k 是介于 i 和 j-1 之间的一个位置）。 合并 [i, k] 的代价是 dp[i][k] ，合并 [k+1, j] 的代价是 dp[k+1][j] 。 最后将这两堆合并的代价是 [i, j] 区间内所有石子的总和，即 prefixSum[j+1] - prefixSum[i] 。 因此，总的代价是这三部分之和。我们需要枚举所有可能的分割点 k ，找到使得总代价最小的那个。 状态转移方程为： dp[i][j] = min( dp[i][k] + dp[k+1][j] + (prefixSum[j+1] - prefixSum[i]) ) ，对于所有满足 i <= k < j 的k。 边界条件 ： 当 i == j 时，只有一堆石子，不需要合并，代价为0。即 dp[i][i] = 0 。 计算顺序 由于计算 dp[i][j] 时需要知道所有更短区间的结果（即 dp[i][k] 和 dp[k+1][j] ），我们应该按照区间长度 len 从小到大的顺序进行计算。 先计算所有长度为1的区间（即单堆石子， dp[i][i] ），然后计算长度为2的区间，接着是长度为3的区间，...，直到长度为 N 的区间。 算法步骤（针对环形问题） 如果石子堆数 N 为0，返回0。如果 N 为1，返回0（因为只有一堆）。 构造一个长度为 2*N 的新数组 newStones ，将原 stones 数组复制两份连接起来。 计算新数组的前缀和数组 prefixSum ，长度为 2*N + 1 。 prefixSum[0] = 0 , prefixSum[i] = newStones[0] + newStones[1] + ... + newStones[i-1] 。 初始化一个大小为 (2*N) x (2*N) 的二维DP数组 dp ，初始值可以设为一个很大的数（比如 INT_MAX ）。 初始化边界条件：对于所有 i 从 0 到 2*N-1 ，设置 dp[i][i] = 0 。 枚举区间长度 len ，从 2 到 N （因为我们需要的是合并成一堆，即长度为N的区间，但我们需要计算所有小于等于N的区间来递推）： 枚举区间起点 i ，从 0 到 2*N - len ： 区间终点 j = i + len - 1 。 枚举分割点 k ，从 i 到 j-1 ： cost = dp[i][k] + dp[k+1][j] + (prefixSum[j+1] - prefixSum[i]) 如果 cost < dp[i][j] ，则更新 dp[i][j] = cost 。 遍历所有可能的起点 i （从0到N-1），对应的区间是 [i, i+N-1] ，找出最小的 dp[i][i+N-1] ，这个值就是环形石子合并的最小总代价。 复杂度分析 时间复杂度：O(N³)。我们需要三重循环：外层循环区间长度O(N)，中层循环起点O(N)，内层循环分割点O(N)。由于我们处理的是长度为2N的数组，但区间长度只枚举到N，所以是O(N * N * N) = O(N³)。 空间复杂度：O(N²)。主要用于存储DP表，大小为(2N) * (2N) ≈ 4N²，即O(N²)。 总结 通过“破环成链”的技巧，我们将环形石子合并问题转化为了一个在扩展线性数组上的区间动态规划问题。核心是定义状态 dp[i][j] 为合并区间[ i, j ]的最小代价，并通过枚举最后一次合并的分割点来建立状态转移关系。最后，在所有可能的长度为N的区间中寻找最小值，即为原环形问题的最优解。