题目描述：
有 $n$ 堆石头排成一排，第 $i$ 堆中有 $stones[i]$ 块石头。
每次移动（move）需要将连续的 $k$ 堆石头合并为一堆，而这个移动的成本为这 $K$ 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 $-1$ 。
数据范围：
$1\le n \le 30;2\le k\le 30$
题解：
与石子合并比较类似，石子合并是区间 $dp$ 做法。递推方程为
其中 $sum(i,k,k+1,j)$ 为合并两堆石子的代价。
使用相同的策略，用 $dp[i][j]$ 表示将区间 $[i,j]$ 中的石子合并之后的最小花费。但是这个合并并不一定能够合并成一堆，可以认为是合并到不能合并为止的最小花费。
$dp[i][j]$ 需要从 $dp[i][k]$ 和 $dp[k + 1][j]$ 转移过来，合并时如果左右两边的还未合并的小堆数量加起来超过了 $k$ ，那么就会产生新的花费。也就是说假如 $k = 3$ ，如果左右两侧分别为 $2$ 堆，那么就会产生新的花费。但是这个合并的代价与左侧一堆，右侧3堆合并的代价相同。因此可以只用枚举 $p = i + m\times(k-1)$ ，只枚举左侧合并为一堆，右侧其他堆的情况就行。
无解的情况，每次合并减少 $k - 1$ 堆，也就是 $n - m\times(k - 1) = 1$ ，即 $(n - 1)\mod (k - 1) = 0$ 是合法的，其他都是非法的。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int dp[31][31] = {};
int mergeStones(vector<int> &stones, int k)
{
int n = stones.size();
if (n < k || (n - 1) % (k - 1))
return -1;
vector<int> sum(n, 0);
sum[0] = stones[0];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i < n; ++i)
{
sum[i] = sum[i - 1] + stones[i];
dp[i][i] = 0;
}
for (int len = 2; len <= n; ++len)
{
for (int i = 0; i + len - 1 < n; ++i)
{
int j = i + len - 1;
for (int p = i; p < j; p += k - 1)
{
dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j] + (!((len - 1) % (k - 1))) * (sum[j] - (i - 1 >= 0 ? sum[i - 1] : 0)));
}
}
}
return dp[0][n - 1];
}
};
|