问题描述: 在一个圆形操场的四周摆放着n堆石子. 现在要将石子有次序地合并成一堆. 规定每次只能选相邻的2堆石子合并成一堆, 并将新的一堆石子数记为该次合并的得分. 试设计一个算法, 计算出将n堆石子合并成一堆的最小得分和最大得分. 算法设计: 对于给定n堆石子, 计算合并成一堆的最小得分和最大得分. 数据输入: 第1行是正整数n, 1<=n<=100, 表示有n堆石子. 第2行有n个数, 分别表示n堆石子的个数. 结果输出: 第1行是最小得分, 第2行是最大得分.

### 回答1：
题目描述：在一个圆形操作场的四周摆放着n堆石子。现在要将石子有序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

算法设计：对于给定n堆石子，计算合并成一堆的最小得分和最大得分。

数据输入: 第1行是整数n，1<=n<=100，表示有n堆石子。第2行有n个数，分别表示n堆石子的个数。

结果输出: 第1行是最小得分，第2行是最大得分。

### 回答2：
这是一道经典的动态规划问题。我们可以设dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小得分和最大得分。

对于最小得分，我们可以先对于每个i，设dp[i][i]=0。因为单独一堆石子不需要合并。接下来我们可以考虑dp[i][j]如何转移。我们可以枚举第k个位置，将第i~j堆分成两边，即第i~k堆和第k+1~j堆，然后将这两边分别合并成一堆，得到总得分sum，然后再加上将这两边合并成的这一堆的石子数，即stones[k]。即dp[i][j]=min(dp[i][j], sum+stones[k]+dp[i][k]+dp[k+1][j])。我们可以从小到大枚举区间长度，即先枚举区间长度为2的情况，然后依次增加。

对于最大得分，我们同样可以对于每个i，设dp[i][i]=0。接下来我们可以考虑dp[i][j]如何转移。我们可以枚举第k个位置，将第i~j堆分成两边，即第i~k堆和第k+1~j堆，然后将这两边分别合并成一堆，得到总得分sum，然后再加上将这两边合并成的这一堆的石子数，即stones[k]。即dp[i][j]=max(dp[i][j], sum+stones[k]).同样我们可以从小到大枚举区间长度，依次增加。

最后我们可以输出dp[1][n]即可得到最小得分和最大得分。时间复杂度为O(n^3)。

### 回答3：
首先，我们可以定义一个dp数组，其中dp[i][j]表示将第i到第j堆石子合并为一堆所需要的最小得分和最大得分。对于任意的i <= j，初始值应该为0。接下来，我们可以按照以下步骤进行动态规划：

1. 枚举区间长度k，从2到n逐个考虑。

2. 对于固定的k，枚举左端点i，右端点j可以通过i+j=k+1得到。例如，当k=4时，可以用(1,4)，(2,3)，(3,2)，(4,1)四个数对分别代表左端点和右端点。

3. 对于当前枚举的区间[i,j]，我们需要枚举中间点p，i <= p < j，将区间[i,j]拆分成两个子区间[i,p],[p+1,j]并计算合并的得分。此时，每个子区间的值可以通过之前已经算出的dp数组中的值得到。

4. 针对当前的合并方式，计算得分并更新dp数组中的值，同时更新最小得分和最大得分。

5. 最终，dp[1][n]就是将n堆石子合并成一堆所需要的最小得分和最大得分。

下面是算法实现的伪代码：

input n
input a1,a2,...,an

initialize dp array with zeros

for k from 2 to n do:
for i from 1 to n-k+1 do:
j = i + k - 1
for p from i to j-1 do:
score = dp[i][p] + dp[p+1][j] + sum(a[i...j])
update dp[i][j] with the min and max score

output dp[1][n][0] as the min score
output dp[1][n][1] as the max score

时间复杂度为O(n^3)， 空间复杂度为O(n^2)。