石子合并

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

• 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 。

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

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

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

输入格式：
数据的第 $1$ 行是正整数 $N$，表示有 $N$ 堆石子。
第 $2$ 行有 $N$ 个整数，第 $i$ 个整数表示第 $i$ 堆石子的个数。

思路分享

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

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

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

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

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

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

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

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

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

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

故有

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

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

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

• “相邻的才可以合并，合并的固定代价为两石堆的石子数之和 $stones[i]+stones[i+1]$” => 计算区间的前缀和进行表示（你可以将前缀和理解为当前石堆及之前石堆石子的总数量）：
  $$\begin{gathered} 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]\text{\hspace{1em}(4)} \end{gathered}$$
  所以进一步的，可以将式(3)写为：

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

你可能发现了上面的式子中 $k$ 的取值范围为 $i..j-1$，这是为了让 $(5)$ 式也能够计算相邻两个石堆合并的代价（$dp[i][i]=0$，所以当 $j=i+1$ 时，$(5)$ 式等于 $(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 = 1
    while (i + length - 1 <= len - 1):
        j = i + length - 1
        dp[i][j] = float("inf")
        for k in range(i, j):	# k的取值范围是 i 到 j-1
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d(i, j)) # 代码等价写法在下面
        i += 1
print(dp[1][N])

C

#include <limits.h> // INT_MAX
#include <stdio.h> // scanf, printf
#include <stdlib.h> // malloc
#include <string.h> // 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);
    }
    
    // 计算dp
    int 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))$等价于下面的代码

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]$ 不一定是合并的最小代价。

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

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

希望你有注意到数组上方圆圈内标注的 ① ② ③ ④，此时 ① 所代表的 $dp[1][4]$ 将不一定是合成的最小代价，需要在最后的输出前对比这四个小区间各自的最小合成代价($dp[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 = 1
    while (i + length - 1 <= len - 1):
        j = i + length - 1
        dpMin[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 <limits.h> // INT_MAX
#include <stdio.h> // scanf, printf
#include <stdlib.h> // malloc
#include <string.h> // 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);
    }
    
    // 计算dp
    int 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 堆）

每次合成 $K$ 堆意味着每次合并后，总堆数减少 $K-1$ 堆。最后需要合并到 $1$ 堆，所以石堆数量 $N$ 需要满足
$$\begin{gathered} N=Z\ast (K-1)+1 \\ \Downarrow \\ 0==(N-1)\%(K-1)\text{\hspace{1em}(1)} \end{gathered}$$
才能合并，所以我们有了第一个条件判断：if (0 != (N - 1) % (K - 1)): 返回 -1。

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

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

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

• $dp[1][3]=d(1,3)$
• $dp[2][4]=d(2,4)$
• $dp[3][5]=d(3,5)$
• $dp[1][4]=min(dp[1][3],dp[2][4])$
• $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)$

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

总结其中规律，有：
$$\begin{gathered} dp[i][j]=\{\begin{array}{llc}{\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)\end{array} \\ 其中k=i,k<j,k\leftarrow k+K-1\text{\hspace{1em}(2)} \end{gathered}$$

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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开始，因为合并时区间长度至少为K
    for (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];
}