石子合并
石子合并问题在网上有三个版本:
-
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 N N 堆石子排成一排,其编号为 1 , 2 , 3 , … , N 1,\ 2,\ 3,\ …\ ,\ N 1, 2, 3, … , N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N N N 堆石子合并成为 1 1 1 堆。
每次只能合并相邻的 2 2 2 堆,合并的代价为这 2 2 2 堆石子数量之和,合并后的相对位置不变。
- 试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分。
- 将这 N N N 堆石子在圆形操场摆放,即首尾堆相连(第 1 1 1 堆和第 N N N 堆),请问此时的最小得分为多少?
- 若一次可合并 K K K 堆,找出把所有石头合并成 1 1 1 堆的最低成本。如果不可能,返回 − 1 -1 −1。
输入格式:
数据的第 1 1 1 行是正整数 N N N,表示有 N N N 堆石子。
第 2 2 2 行有 N N N 个整数,第 i i i 个整数表示第 i i i 堆石子的个数。
思路分享
一个错误的思路:局部最优解
一开始看到这题很容易联想到曾经学过的哈夫曼编码思路(多加个相邻的约束条件),我也尝试过编写该代码,发现不讨巧的情况下只能通过 6 / 10 6/10 6/10 的测试样例。因为它是一种贪心算法,只考虑到了当前情况下的最优解,下面我会给出样例进行解释。
你应该注意到上面第二小问删去了最大得分的部分,这是因为它的动归写法和最小得分思路一样,但为了更清晰的否定掉“哈夫曼编码”在此题的思路,我需要引用一个最大得分的反例:
可以从下图看到第一次合并有两种组合,分别为左侧的 6, 12
和右侧的 3, 15
,如果我们按照贪心算法,去选择第一次遇到的最大组合,会发现得到的最大值为 158
,而实际上正确答案为右侧的 171
。
当然你选最后一次的最大组合是一样的,只需要将当前输入的序列逆置一下就能发现错误(碎碎念:可以用这个方法来通过LibreOJ上 7 / 10 7/10 7/10 的测试样例)。
第一问(排成一排)-- 动态规划
利用 dp 数组
存储最小的合并代价:第
i
i
i 个石堆到第
j
j
j 个石堆的最小合并代价为
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]。
只有一个石堆时,最小合并代价为0,设
d
p
[
i
]
[
i
]
=
0
,
i
=
1..
N
dp[i][i] = 0, i = 1..N
dp[i][i]=0,i=1..N。
注意,为了表达方便:这里第
i
i
i 堆石子对应的下标就是
i
i
i 而非
i
−
1
i-1
i−1。
想一下最简单的合并情况:相邻两个石堆
i
i
i 和石堆
i
+
1
i + 1
i+1 ,它们合并代价是两个石堆石子数的总和,即
d
p
[
i
]
[
i
+
1
]
=
s
t
o
n
e
s
[
i
]
+
s
t
o
n
e
s
[
i
+
1
]
(1)
dp[i][i+1] = stones[i] + stones[i+1] \tag{1}
dp[i][i+1]=stones[i]+stones[i+1](1)
那么非相邻的两个石堆之间的合并代价又是什么呢?
因为每次只能合并相邻的两堆,石堆 i i i 想与石堆 j j j 合并成一堆前,必然要经过相邻两个石堆的合并,也就是说存在石堆 k k k 将石堆 ( i . . . j ) (i...j) (i...j) 划分为 ( i . . . k ) (i...k) (i...k) 和 ( k + 1... j ) (k+1...j) (k+1...j) ,这两个石堆的合并代价分别为 d p [ i ] [ k ] dp[i][k] dp[i][k] 和 d p [ k + 1 ] [ j ] dp[k+1][j] dp[k+1][j]。
回顾下 dp 数组
的定义:存储最小的合并代价(指的是合并的总代价,总代价 = 每次石子合并的代价之和)。
故有
而两石堆的石子数之和是显然的,这里给出最后的公式:
其实这是一个区间动态规划问题:
-
“排成一排的 N N N 堆石子” => N N N 个连续的小区间。
-
“相邻的才可以合并,合并的固定代价为两石堆的石子数之和 s t o n e s [ i ] + s t o n e s [ i + 1 ] stones[i] + stones[i+1] stones[i]+stones[i+1]” => 计算区间的前缀和进行表示(你可以将前缀和理解为当前石堆及之前石堆石子的总数量):
s [ 0 ] = 0 s [ i ] = s [ i − 1 ] + s t o n e s [ i ] s t o n e s [ i ] + s t o n e s [ i + 1 ] = s [ i + 1 ] − s [ i − 1 ] ⇓ s t o n e s [ i ] + . . . + s t o n e s [ k ] + s t o n e s [ k + 1 ] + . . . + s t o n e s [ 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) 式其实是就是我们代码的核心。
你可能发现了上面的式子中 k k k 的取值范围为 i . . j − 1 i..j-1 i..j−1,这是为了让 ( 5 ) (5) (5) 式也能够计算相邻两个石堆合并的代价( d p [ i ] [ i ] = 0 dp[i][i] = 0 dp[i][i]=0,所以当 j = i + 1 j = i+1 j=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 = 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;
}
d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ 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;
第二问(排成一圈)
第二问较第一问的区别是石子在圆形操场排成一圈,也就是说现在 d p [ 1 ] [ N ] dp[1][N] dp[1][N] 不一定是合并的最小代价。
以下面的输入为例进行解释。
下图为排列状况,排成一圈相当于 4 4 4 到 1 1 1 的路径通了,原来的数组变成了循环数组,乍一看好像很复杂,但实际上可以将其化简成右下角非循环的格式: 1 2 3 4 1 2 3 1\ 2\ 3\ 4\ 1\ 2\ 3 1 2 3 4 1 2 3
希望你有注意到数组上方圆圈内标注的 ① ② ③ ④,此时 ① 所代表的
d
p
[
1
]
[
4
]
dp[1][4]
dp[1][4] 将不一定是合成的最小代价,需要在最后的输出前对比这四个小区间各自的最小合成代价(
d
p
[
i
]
[
i
+
N
−
1
]
,
i
=
1..
N
,
N
=
4
dp[i][i+N-1], i = 1..N, N = 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
K 堆意味着每次合并后,总堆数减少
K
−
1
K-1
K−1 堆。最后需要合并到
1
1
1 堆,所以石堆数量
N
N
N 需要满足
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 = 2 K=2 K=2 时,任意数量的石堆均能合并成 1 1 1 堆,而此时 0 = = N % ( K − 1 ) 0 ==N\ \%\ (K-1) 0==N % (K−1) 。
第三问中,dp数组
同样表示最小合成代价,但这个最小合成代价的指的是合并到不能合并为止时到最小代价,也就是说:当
N
>
K
N > K
N>K 时,即使
N
N
N 不满足最后合成到
1
1
1 堆的条件,
d
p
[
1
]
[
N
]
dp[1][N]
dp[1][N] 也不为
0
0
0。当然,还需要注意到的是:在最开始的条件判断中,无法合并为
1
1
1 堆的石堆已经被筛除了,我们现在这样设计的目的是为了方便求得
d
p
[
1
]
[
N
]
dp[1][N]
dp[1][N],其中
0
=
=
(
N
−
1
)
%
(
K
−
1
)
0 == (N-1)\ \%\ (K - 1)
0==(N−1) % (K−1)。
令
N
=
5
N = 5
N=5,来看看 dp数组
的取值。
- d p [ 1 ] [ 3 ] = d ( 1 , 3 ) dp[1][3] = d(1,3) dp[1][3]=d(1,3)
- d p [ 2 ] [ 4 ] = d ( 2 , 4 ) dp[2][4] = d(2,4) dp[2][4]=d(2,4)
- d p [ 3 ] [ 5 ] = d ( 3 , 5 ) dp[3][5] = d(3,5) dp[3][5]=d(3,5)
- d p [ 1 ] [ 4 ] = m i n ( d p [ 1 ] [ 3 ] , d p [ 2 ] [ 4 ] ) dp[1][4] = min(dp[1][3], dp[2][4]) dp[1][4]=min(dp[1][3],dp[2][4])
- d p [ 2 ] [ 5 ] = m i n ( d p [ 2 ] [ 4 ] , d p [ 3 ] [ 5 ] ) dp[2][5] = min(dp[2][4], dp[3][5]) dp[2][5]=min(dp[2][4],dp[3][5])
- d p [ 1 ] [ 5 ] = m i n ( d p [ 1 ] [ 4 ] , d p [ 2 ] [ 5 ] ) + d ( 1 , 5 ) = m i n ( d p [ 1 ] [ 3 ] , d p [ 2 ] [ 4 ] , d p [ 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
.
.
j
i..j
i..j 堆石堆可以合并成一堆,此时
d
p
[
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
.
.
j
i..j
i..j 堆石堆不能合并成一堆,此时
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 等于合成到
<
K
<K
<K 堆时的最小合成代价。文章来源:https://www.toymoban.com/news/detail-781895.html
总结其中规律,有:
d
p
[
i
]
[
j
]
=
{
min
k
(
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
)
+
d
(
i
,
j
)
,
0
=
=
(
j
−
i
)
%
(
K
−
1
)
min
k
(
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
)
,
0
!
=
(
j
−
i
)
%
(
K
−
1
)
其
中
k
=
i
,
k
<
j
,
k
←
k
+
K
−
1
(2)
dp[i][j]= \begin{cases} \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{cases} \\其中 k=i,\ k<j,\ k \leftarrow k+K-1 \tag{2}
dp[i][j]={mink(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<j, k←k+K−1(2)文章来源地址https://www.toymoban.com/news/detail-781895.html
#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];
}
到了这里,关于石子合并系列问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!