一、Problem
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Note:
1 <= stones.length <= 30 2 <= K <= 30 1 <= stones[i] <= 100
二、Solution
方法一：记忆化搜索
定义状态：
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] 表示将区间
[
i
,
j
]
[i, j]
[i,j] 中的几堆石子合并成
k
k
k 堆需要的最小代价 思考初始化：
f
[
0
:
]
[
0
:
]
[
0
:
]
=
I
N
F
f[0:][0:][0:] = INF
f[0:][0:][0:]=INF
f
[
i
]
[
i
]
[
1
]
=
0
f[i][i][1] = 0
f[i][i][1]=0 石子不用动就可以了… 思考状态转移方程：
这里直接写转移会比较繁琐，所以直接讲思路：因为我们不知道合并哪些区间可以使得代价最小，所以我们需要穷举一下每种大小的区间 len（len = r-l+1）且在区间 [l, r] 中，我们也不清楚具体要合并哪两对堆（如果将区间划分成两半）所以我们需要枚举一下切分点 p 在区间 [l, r] 中的位置切分位置 p 我们知道了，但是我们还不知道要将这两部分石子合并成几堆，所以我们还需要枚举一下石子的对数
k
（
k
⩽
r
−
l
+
1
）
k（k \leqslant r-l+1）
k（k⩽r−l+1） 思考输出：
f
[
1
]
[
n
]
[
1
]
f[1][n][1]
f[1][n][1]
class Solution {
public int mergeStones(int[] a
, int K
) {
int n
= a
.length
, INF
= 0x3f3f3f3f, s
[] = new int[n
+1], f
[][][] = new int[n
+1][n
+1][n
+1];
if ((n
-1) % (K
-1) != 0)
return -1;
if (n
< 2)
return 0;
for (int i
= 1; i
<= n
; i
++)
for (int j
= 1; j
<= n
; j
++) {
Arrays
.fill(f
[i
][j
], INF
);
}
for (int i
= 1; i
<= n
; i
++) {
s
[i
] = s
[i
-1] + a
[i
-1];
f
[i
][i
][1] = 0;
}
for (int len
= 2; len
<= n
; len
++)
for (int l
= 1; l
<= n
- len
+ 1; l
++) {
int r
= l
+ len
- 1;
for (int k
= 2; k
<= len
; k
++)
for (int p
= l
; p
< r
; p
++) {
f
[l
][r
][k
] = Math
.min(f
[l
][r
][k
], f
[l
][p
][k
-1] + f
[p
+1][r
][1]);
}
f
[l
][r
][1] = Math
.min(f
[l
][r
][1], f
[l
][r
][K
] + s
[r
] - s
[l
-1]);
}
return f
[1][n
][1];
}
}
复杂度分析
时间复杂度：
O
(
n
3
×
K
)
O(n^3 × K)
O(n3×K)，空间复杂度：
O
(
n
3
)
O(n^3)
O(n3)，
