题目描述

有 n 堆石子排成一排，其编号为 1, 2, 3, ..., n（n ≤ 100）。每堆石子有一定的数量。例如有 7 堆石子，分别为：13, 7, 8, 16, 21, 4, 18。

现在要将 n 堆石子归并成一堆。归并的过程是每次只能将相邻的两堆石子合并成一堆，这样经过 n-1 次归并后成为一堆。不同的归并方法会导致不同的归并代价。归并代价是指在每次归并时，两个石子的堆合并时会产生一个代价，这个代价是两堆石子的总数量。

例如，假设有 7 堆石子，具体堆数为：

13, 7, 8, 16, 21, 4, 18

则（a）的归并代价为：20 + 24 + 25 + 44 + 69 + 87 = 267

而（b）的归并代价为：15 + 37 + 22 + 28 + 59 + 87 = 248

从中我们可以看到，不同的归并顺序得到的归并代价不同。你的任务是编程找出一种合理的方法，使归并代价最小。

输入格式

• 第一行：一个整数 n，表示石子的堆数。
• 第二行：n 个整数，表示每堆石子的数量。

输出格式

• 输出一个整数，表示最小的归并代价。

样例输入

7
13 7 8 16 21 4 18

样例输出

248

提示

• 对于 n = 2 时，只有一种归并方式，代价为两堆石子数量的和。
• 对于 n = 3 时，存在两种归并方式，其中最小的代价为 54 和 55，注意最后的代价是所有堆石子的数量和。
• 对于 n = 4 时，存在 5 种归并方式，最小代价可能出现在不同的归并策略下。归并代价的最终求解与归并的顺序密切相关。

思路

该问题实际上是一个 ​动态规划问题​，可以通过动态规划来寻找最优的归并顺序。我们需要通过枚举不同的归并顺序来计算不同的代价，并找到最小代价。

1. 定义状态：

我们定义一个二维数组 dp[i][j]，表示合并从第 i 堆到第 j 堆石子的最小代价。

2. 状态转移：

• 如果我们要合并区间 [i, j]，我们可以尝试把这个区间分成两个子区间 [i, k] 和 [k+1, j]，然后合并这两个子区间。合并代价是两个子区间的代价之和加上这两个子区间的总石子数。

3. 最终结果：

最后，dp[1][n] 就是将所有堆石子合并成一堆的最小代价。

动态规划转移公式：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i, j))  for all k in [i, j-1]

其中 sum(i, j) 表示从第 i 堆到第 j 堆所有石子数的总和。

复杂度分析：

时间复杂度为 O(n^3)，其中 n 是堆的数量。由于 n ≤ 100，所以该解法在时间限制内是可行的。

样例分析：

输入：

7
13 7 8 16 21 4 18

输出：

248

结论：

通过动态规划，可以高效地计算出最小的归并代价，避免了暴力枚举所有可能的归并顺序。