算法设计：带加权计分的石子合并游戏

给定大小为n+1的石子数组，每个石子初始重量为1。游戏规则如下：

• 从第0轮开始，每轮选择任意两个相邻石子合并，合并后新石子重量为两石子重量之和x+y。
• 本轮需支付成本x*y*v[j]，其中v[j]是预先给定的非递增序列。
• 经过n轮后需仅剩一个重量为n+1的石子，目标是最小化总成本。

示例 #

示例1 #

输入：n=5, v=[4,3,2,0,0]
输出：9
解释：合并过程为 [1 1 1 1 1 1]->[2 1 1 1 1]->[2 2 1 1]->[2 2 2]->[4 2]->[6]，总成本为 1*1*4 + 1*1*3 + 1*1*2 = 9

示例2 #

输入：n=5, v=[4,3,1,1,0]
输出：11
解释：合并过程为 [1 1 1 1 1 1]->[2 1 1 1 1]->[2 1 2 1]->[3 2 1]->[3 3]->[6]，总成本为 1*1*4 + 1*1*3 + 2*1*1 + 2*1*1 = 11

示例3 #

输入：n=5, v=[4,2,2,1,0]
输出：12

已尝试方法的局限 #

• 贪心策略：之前尝试的贪心逻辑错误（如优先合并大权重对），无法得到最优解。
• 初步动态规划尝试：未找到正确的状态定义与转移方式，未能实现多项式时间复杂度。

多项式时间解决方案 #

核心思路：排序不等式的应用 #

由于v是非递增序列（v[0] ≥ v[1] ≥ ... ≥ v[n-1]），根据排序不等式，要让总成本最小，需满足合并操作的x*y值随轮次递增——即让小的x*y乘大的v[j]，大的x*y乘小的v[j]。

基于此，最优策略为：每一轮选择当前所有相邻石子对中x*y最小的进行合并。

算法实现：最小堆+链表维护 #

步骤：

1. 数据结构初始化：
   • 用链表（或数组+左右指针）维护当前石子的重量及相邻关系，初始时所有石子重量为1。
   • 用最小堆存储所有相邻石子对的x*y值，同时记录该对的左右石子索引（需标记无效对，避免重复处理）。
2. 逐轮合并：
   对于每一轮t（从0到n-1）：
   a. 从堆中取出最小的x*y值对应的有效相邻对。
   b. 合并这两个相邻石子，得到新重量x+y。
   c. 累加本轮成本：x*y * v[t]到总成本。
   d. 更新链表：删除原两个石子节点，插入新石子节点，并维护新节点与左右邻居的相邻关系。
   e. 将新节点与左右邻居形成的新相邻对的x*y值加入堆中。
3. 结束：完成n轮合并后，输出总成本。

时间复杂度

总共有O(n)次合并操作，每次堆操作的时间为O(log n)，因此整体时间复杂度为O(n log n)，属于多项式时间。

备选方案：动态规划（O(n³)） #

若偏好动态规划实现，可采用如下定义：

• 状态定义：dp[i][j]表示合并第i到第j个初始石子（共j-i+1个）的最小总成本。

• 初始化：当i == j时，dp[i][j] = 0（无需合并）。

• 状态转移：
  对于区间[i,j]（长度m = j-i+1 ≥2），遍历所有分割点k（i ≤k <j），计算：

  dp[i][j] = min(dp[i][k] + dp[k+1][j] + (k-i+1)*(j-k) * v[ (n-1) - (m-2) ])
  

  其中(m-1)是合并该区间所需的操作次数，(n-1) - (m-2)表示该区间最后一次合并（即合并两个子区间的操作）对应的v索引——因为大的x*y要对应小的v，所以最后一次合并用较晚的v值。

  该方法时间复杂度为O(n³)，适用于n较小的场景。

内容的提问来源于stack exchange，提问作者OptAlg