石子合并

石子合并问题在网上有三个版本：

• AcWing 282. 石子合并
  设有 N 堆石子排成一排，其编号为 1，2，3，…，N。

  每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

  每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
  找出一种合理的方法，使总的代价最小，输出最小代价。

• LibreOJ #10147. 「一本通 5.1 例 1」石子合并 / 洛谷 P1880 [NOI1995] 石子合并

  将 N 堆石子绕圆形操场摆放，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。

  试设计出一个算法,计算出将 N 堆石子合并成1堆的最小得分和最大得分。

• LeetCode 1000. 合并石头的最低成本
  有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

  每次*移动（move）*需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。

  找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

为了方便讲述和理解，可以将上述三题总结为一题的三个小问进行表达：

有 NNN 堆石子排成一排，其编号为 1,2,3,…,N1,\ 2,\ 3,\ …\ ,\ N1, 2, 3, … , N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 NNN 堆石子合并成为 111 堆。
每次只能合并相邻的 222 堆，合并的代价为这 222 堆石子数量之和，合并后的相对位置不变。

1. 试设计出一个算法,计算出将 NNN 堆石子合并成 111 堆的最小得分。
2. 将这 NNN 堆石子在圆形操场摆放，即首尾堆相连（第 111 堆和第 NNN 堆），请问此时的最小得分为多少？
3. 若一次可合并 KKK 堆，找出把所有石头合并成 111 堆的最低成本。如果不可能，返回 −1-1−1。

输入格式：
数据的第 111 行是正整数 NNN，表示有 NNN 堆石子。
第 222 行有 NNN 个整数，第 iii 个整数表示第 iii 堆石子的个数。

思路分享

一个错误的思路：局部最优解

一开始看到这题很容易联想到曾经学过的哈夫曼编码思路（多加个相邻的约束条件），我也尝试过编写该代码，发现不讨巧的情况下只能通过 6/106/106/10 的测试样例。因为它是一种贪心算法，只考虑到了当前情况下的最优解，下面我会给出样例进行解释。

你应该注意到上面第二小问删去了最大得分的部分，这是因为它的动归写法和最小得分思路一样，但为了更清晰的否定掉“哈夫曼编码”在此题的思路，我需要引用一个最大得分的反例：

可以从下图看到第一次合并有两种组合，分别为左侧的 6, 12 和右侧的 3, 15，如果我们按照贪心算法，去选择第一次遇到的最大组合，会发现得到的最大值为 158，而实际上正确答案为右侧的 171。

当然你选最后一次的最大组合是一样的，只需要将当前输入的序列逆置一下就能发现错误（碎碎念：可以用这个方法来通过LibreOJ上 7/107/107/10 的测试样例）。

第一问（排成一排）-- 动态规划

利用 dp 数组 存储最小的合并代价：第 iii 个石堆到第 jjj 个石堆的最小合并代价为 dp[i][j]dp[i][j]dp[i][j]。
只有一个石堆时，最小合并代价为0，设 dp[i][i]=0,i=1..Ndp[i][i] = 0, i = 1..Ndp[i][i]=0,i=1..N。
注意，为了表达方便：这里第 iii 堆石子对应的下标就是 iii 而非 i−1i-1i−1。

想一下最简单的合并情况：相邻两个石堆 iii 和石堆 i+1i + 1i+1 ，它们合并代价是两个石堆石子数的总和，即
dp[i][i+1]=stones[i]+stones[i+1](1)dp[i][i+1] = stones[i] + stones[i+1] \tag{1} dp[i][i+1]=stones[i]+stones[i+1](1)
那么非相邻的两个石堆之间的合并代价又是什么呢？

因为每次只能合并相邻的两堆，石堆 iii 想与石堆 jjj 合并成一堆前，必然要经过相邻两个石堆的合并，也就是说存在石堆 kkk 将石堆 (i...j)(i...j)(i...j) 划分为 (i...k)(i...k)(i...k) 和 (k+1...j)(k+1...j)(k+1...j) ，这两个石堆的合并代价分别为 dp[i][k]dp[i][k]dp[i][k] 和 dp[k+1][j]dp[k+1][j]dp[k+1][j]。

回顾下 dp 数组 的定义：存储最小的合并代价（指的是合并的总代价，总代价 = 每次石子合并的代价之和）。

故有

而两石堆的石子数之和是显然的，这里给出最后的公式:

其实这是一个区间动态规划问题：

• “排成一排的 NNN 堆石子” => NNN 个连续的小区间。

• “相邻的才可以合并，合并的固定代价为两石堆的石子数之和 stones[i]+stones[i+1]stones[i] + stones[i+1]stones[i]+stones[i+1]” => 计算区间的前缀和进行表示（你可以将前缀和理解为当前石堆及之前石堆石子的总数量）：
  s[0]=0s[i]=s[i−1]+stones[i]stones[i]+stones[i+1]=s[i+1]−s[i−1]⇓stones[i]+...+stones[k]+stones[k+1]+...+stones[j]=s[j]−s[i−1](4)s[0] = 0\\ s[i] = s[i-1] + stones[i]\\ stones[i] + stones[i+1] = s[i+1] - s[i-1]\\ \Downarrow\\ stones[i]+...+stones[k]+ stones[k+1]+...+stones[j] = s[j] - s[i-1] \tag{4} s[0]=0s[i]=s[i−1]+stones[i]stones[i]+stones[i+1]=s[i+1]−s[i−1]⇓stones[i]+...+stones[k]+stones[k+1]+...+stones[j]=s[j]−s[i−1](4)
  所以进一步的，可以将式(3)写为：

(i,k)(i, k)(i,k) 和$ (k+1, j)$ 本身可以再划分成两小堆，因此 (5)(5)(5) 式其实是就是我们代码的核心。

你可能发现了上面的式子中 kkk 的取值范围为 i..j−1i..j-1i..j−1，这是为了让 (5)(5)(5) 式也能够计算相邻两个石堆合并的代价（dp[i][i]=0dp[i][i] = 0dp[i][i]=0，所以当 j=i+1j = i+1j=i+1 时，(5)(5)(5) 式等于 (1)(1)(1) 式）。

现在可以来编写代码来完成这题。

代码

Python

# 处理输入（只有LeetCode不需要处理）
N = int(input())
stones = [0] + list(map(int, input().split()))
len = N + 1# 计算前缀和
s = [0] * len
for i in range(1, len):s[i] = s[i - 1] + stones[i]# dp数组初始化
dp = [[0] * (len) for _ in range(len)]# 用d(i, j)表示s[j] - s[i - 1]
d = lambda i, j: s[j] - s[i - 1]# 计算dp，length从2开始，因为区间长度（石头堆数）至少为2时才能合并
for length in range(2, N + 1):i = 1while (i + length - 1 <= len - 1):j = i + length - 1dp[i][j] = float("inf")for k in range(i, j):	# k的取值范围是 i 到 j-1dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i, j)) # 代码等价写法在下面i += 1
print(dp[1][N])

C

#include  // INT_MAX
#include  // scanf, printf
#include  // malloc
#include  // memset#define d(i, j) (s[j]-s[i-1]) // 用d(i, j)表示s[j] - s[i - 1]
#define min(x, y) ((x)<(y)?(x):(y))int main(){// 处理输入int N, *stones, len;scanf("%d", &N);len = N + 1;stones = (int *)malloc(sizeof(int) * len);for (int i = 1; i <= N; i++){scanf("%d", &stones[i]);}// 计算前缀和int *s = (int *)malloc(sizeof(int) * len);memset(s, 0, sizeof(int) * len);for (int i = 1; i < len; i++)s[i] = s[i - 1] + stones[i];// dp数组初始化int **dp = (int **)malloc(sizeof(int *) * len);for (int i = 0; i < len; i++){dp[i] = (int *)malloc(sizeof(int) * len);memset(dp[i], 0, sizeof(int) * len);}// 计算dpint length, i, j, k;// length从2开始，因为区间长度（石头堆数）至少为2时才能合并for (length = 2; length <= N; length++){i = 1;for (j = i + length - 1; j <= len - 1; j++){dp[i][j] = INT_MAX;for (k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j)); // 代码等价写法在下面i += 1;}}printf("%d", dp[1][N]);return 0;
}

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+d(i,j))dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j))dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+d(i,j))等价于下面的代码

int tmp = dp[i][j];
dp[i][j] = dp[i][k] + dp[k + 1][j] + d(i,j);
if (tmp < dp[i][j])dp[i][j] = tmp;

第二问（排成一圈）

第二问较第一问的区别是石子在圆形操场排成一圈，也就是说现在 dp[1][N]dp[1][N]dp[1][N] 不一定是合并的最小代价。

以下面的输入为例进行解释。

下图为排列状况，排成一圈相当于 444 到 111 的路径通了，原来的数组变成了循环数组，乍一看好像很复杂，但实际上可以将其化简成右下角非循环的格式：12341231\ 2\ 3\ 4\ 1\ 2\ 31 2 3 4 1 2 3

希望你有注意到数组上方圆圈内标注的 ① ② ③ ④，此时 ① 所代表的 dp[1][4]dp[1][4]dp[1][4] 将不一定是合成的最小代价，需要在最后的输出前对比这四个小区间各自的最小合成代价(dp[i][i+N−1],i=1..N,N=4dp[i][i+N-1], i = 1..N, N = 4dp[i][i+N−1],i=1..N,N=4），来找到真正的最小值，也就是：

到这步，其实已经完成了第一问到第二问代码的转换：

Python

N = int(input())
- stones = [0] + list(map(int, input().split()))
+ stones = [0] + (list(map(int, input().split())) * 2)[:-1]
- len = N + 1
+ len = N + N# 前缀和
s = [0] * len
for i in range(1, len):s[i] = s[i - 1] + stones[i]dpMax = [[0] * (len) for _ in range(len)]
dpMin = [[0] * (len) for _ in range(len)]d = lambda i, j: s[j] - s[i - 1]
for length in range(2, N + 1):i = 1while (i + length - 1 <= len - 1):j = i + length - 1dpMin[i][j] = float("inf")for k in range(i, j):dpMin[i][j] = min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j] + d(i, j))i += 1- print(dp[1][N])
+ minl = float("inf")
+ for i in range(1, N + 1):
+	minl = min(minl, dpMin[i][i + N - 1])
+ print(minl)

C

#include  // INT_MAX
#include  // scanf, printf
#include  // malloc
#include  // memset#define d(i, j) (s[j]-s[i-1]) // 用d(i, j)表示s[j] - s[i - 1]
#define min(x, y) ((x)<(y)?(x):(y))int main(){// 处理输入int N, *stones, len;scanf("%d", &N);
-   len = N + 1;
+	len = N + N + 1;stones = (int *)malloc(sizeof(int) * len);for (int i = 1; i <= N; i++){scanf("%d", &stones[i]);
+       stones[i + N] = stones[i];}// 计算前缀和int *s = (int *)malloc(sizeof(int) * len);memset(s, 0, sizeof(int) * len);for (int i = 1; i < len; i++)s[i] = s[i - 1] + stones[i];// dp数组初始化int **dp = (int **)malloc(sizeof(int *) * len);for (int i = 0; i < len; i++){dp[i] = (int *)malloc(sizeof(int) * len);memset(dp[i], 0, sizeof(int) * len);}// 计算dpint length, i, j, k;// length从2开始，因为区间长度（石头堆数）至少为2时才能合并for (length = 2; length <= N; length++){i = 1;for (j = i + length - 1; j <= len - 1; j++){dp[i][j] = INT_MAX;for (k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i,j)); i += 1;}}
+   int minl = INT_MAX;
+ 	for (i = 1; i <= N; i++)
+    	minl = min(minl, dpMin[i][i + N - 1]);-   printf("%d", dp[1][N]);
+   printf("%d\n", minl);return 0;
}

第三问（每次合成 K 堆）

每次合成 KKK 堆意味着每次合并后，总堆数减少 K−1K-1K−1 堆。最后需要合并到 111 堆，所以石堆数量 NNN 需要满足
N=Z∗(K−1)+1⇓0==(N−1)%(K−1)(1)N = Z * (K - 1) + 1\\ \Downarrow\\ 0 == (N-1)\ \%\ (K - 1) \tag{1} N=Z∗(K−1)+1⇓0==(N−1) % (K−1)(1)
才能合并，所以我们有了第一个条件判断：if (0 != (N - 1) % (K - 1)): 返回 -1。

注意，不能仅使用看起来等价的 1==N%(K−1)1 == N\ \%\ (K-1)1==N % (K−1) ，因为当 K=2K=2K=2 时，任意数量的石堆均能合并成 111 堆，而此时0==N%(K−1)0 ==N\ \%\ (K-1)0==N % (K−1) 。

第三问中，dp数组 同样表示最小合成代价，但这个最小合成代价的指的是合并到不能合并为止时到最小代价，也就是说：当 N>KN > KN>K 时，即使 NNN 不满足最后合成到 111 堆的条件，dp[1][N]dp[1][N]dp[1][N] 也不为 000。当然，还需要注意到的是：在最开始的条件判断中，无法合并为 111 堆的石堆已经被筛除了，我们现在这样设计的目的是为了方便求得 dp[1][N]dp[1][N]dp[1][N]，其中 0==(N−1)%(K−1)0 == (N-1)\ \%\ (K - 1)0==(N−1) % (K−1)。

令 N=5N = 5N=5，来看看 dp数组 的取值。

• dp[1][3]=d(1,3)dp[1][3] = d(1,3)dp[1][3]=d(1,3)
• dp[2][4]=d(2,4)dp[2][4] = d(2,4)dp[2][4]=d(2,4)
• dp[3][5]=d(3,5)dp[3][5] = d(3,5)dp[3][5]=d(3,5)
• dp[1][4]=min(dp[1][3],dp[2][4])dp[1][4] = min(dp[1][3], dp[2][4])dp[1][4]=min(dp[1][3],dp[2][4])
• dp[2][5]=min(dp[2][4],dp[3][5])dp[2][5] = min(dp[2][4], dp[3][5])dp[2][5]=min(dp[2][4],dp[3][5])
• dp[1][5]=min(dp[1][4],dp[2][5])+d(1,5)=min(dp[1][3],dp[2][4],dp[3,5])+d(1,5)dp[1][5] = min(dp[1][4], dp[2][5]) + d(1,5) = min(dp[1][3], dp[2][4], dp[3,5]) + d(1,5)dp[1][5]=min(dp[1][4],dp[2][5])+d(1,5)=min(dp[1][3],dp[2][4],dp[3,5])+d(1,5)

当 0==(j−i)%(K−1)0 == (j - i) \% (K - 1)0==(j−i)%(K−1) 时，i..ji..ji..j 堆石堆可以合并成一堆，此时 dp[i][j]dp[i][j]dp[i][j] 需要计算最后一次合并的代价 d(i,j)d(i,j)d(i,j)。
当 0!=(j−i)%(K−1)0\ \ != (j - i) \% (K - 1)0  !=(j−i)%(K−1) 时，i..ji..ji..j 堆石堆不能合并成一堆，此时 dp[i][j]dp[i][j]dp[i][j] 等于合成到

总结其中规律，有：
dp[i][j]={min⁡k(dp[i][k]+dp[k+1][j])+d(i,j),0==(j−i)%(K−1)min⁡k(dp[i][k]+dp[k+1][j]),0!=(j−i)%(K−1)其中k=i,kmink​(dp[i][k]+dp[k+1][j])+d(i,j),mink​(dp[i][k]+dp[k+1][j]),​​0==(j−i)%(K−1)0  !=(j−i)%(K−1)​其中k=i, k

#include 
#include 
#include 
#include #define d(i, j) (s[j]-s[i-1])
#define min(x, y) ((x)<(y)?(x):(y))int mergeStones(int* stones, int N, int K){int len, *nums;// 每次合并减少k-1个石堆，最后需要剩一个if (0 != (N - 1) % (K - 1)) // 等价于 K != 2 && 1 != stonesSize % (K - 1))return -1;len = N + 1;// 计算前缀和int *s = (int *)malloc(sizeof(int) * len);memset(s, 0, sizeof(int) * len);for (int i = 1; i < len; i++)s[i] = stones[i - 1] + s[i - 1];// dp数组初始化int **dpMin = (int **)malloc(sizeof(int *) * len);for (int i = 0; i < len; i++){dpMin[i] = (int *)malloc(sizeof(int *) * len);memset(dpMin[i], 0, sizeof(int) * len);}int length, i, j, k;// length从K开始，因为合并时区间长度至少为Kfor (length = K; length <= N; length++){i = 1;for (j = i + length - 1; j <= len - 1; j++){dpMin[i][j] = INT_MAX;for (k = i; k < j; k += K-1){dpMin[i][j] = min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j]);}if (0 == (length - 1) % (K - 1)) // 式（2）dpMin[i][j] += d(i, j);i += 1;}}return dpMin[1][N];
}