石子合并 动态规划

有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。

输入

有多组测试数据,输入到文件结束。
每组测试数据第一行有一个整数n,表示有n堆石子。
接下来的一行有n( 0< n < 200)个数,分别表示这n堆石子的数目,用空格隔开

输出

输出总代价的最小值,占单独的一行

样例输入

样例输出


解题思路

题目如上述所说的一样,思路是动态规划不假,但是我就不扯那些生硬的动态规划的,这里讲一个例子解释以下这道题。
假设我们有 5 个石子分别是

序号 1 2 3 4 5
重量 1 2 3 4 5

这里先分解一下问题:

假设只要求序号区间 [1,2] 之间的石子合并最优解,很明显,3 就是答案。同理我们很容易得出如下的表格:

序号区间 最优解
1,2 3
2,3 5
3,4 7
4,5 9

那稍微难一点,我们计算区间 [1, 3] 之间的石子合并最优解,可以这么理解:

  1. 首先模拟一下合并过程
    下面是区间 1, 3 的最优合并示例

说白了, 就是 区间 [1, 2] 和区间 [3,3] 求和, 并且加上 sum(1,3)(所有石子的质量)

  1. 实际计算机会有这么一个过程

    1. [1, 3] 之间可以分化为两个子区间 [1, 1] + [2, 3].
    2. [1, 3] 还可以分化为另外两个子区间 [1, 2] + [3, 3].

而上述的每一个子区间的最优解我们都知道, 分别是 0([1, 1] 没有移动, 自然为零) 和 5 (查表). 我们只需要计算两者哪一个是最优解.

我们看 [1, 3] 区间的结果应该是 [2, 3] 的 5, 然后这个 5 再叠加上 5 本身和 1 本身, 换句话说, 就是 [2, 3] + sum(1, 3). 此时我们即得到了 [1, 3] 之间的最优解. 如果这里没看明白, 反复看上述模拟合并的过程.

注释: sum(1, 3) 区间内的石子重量之和.

同理, 我们要一层一层的求出 5 以内的每一个区间的最优解. 这里建立一张二维 db[5][5] 表, 表示每一个区间 dp[i][j] 的最优解.

1 2 3 4 5
1 0 3
2 0 5
3 0 7
4 0 9
5 0

注释 :
1. 本身到本身的消耗为零
2. 横排排头表示 j 序列
3. 纵排排头表示 i 序列
4. 表中数据 3, 即为区间 [1, 3] 间的最优解 dp[1][3].

1 2 3 4 5
1 0 3 9
2 0 5 14
3 0 7 19
4 0 9
5 0

之后:

1 2 3 4 5
1 0 3 9 19
2 0 5 14 28
3 0 7 19
4 0 9
5 0

比如数据 19, 区间 1-4 的最优解, 可以分化为
1. 1-1,2-4
2. 1-2,3-4
3. 1-3,4-4
这里我们查表即可求得最优解 19;

最后:

1 2 3 4 5
1 0 3 9 19 33
2 0 5 14 28
3 0 7 19
4 0 9
5 0

返回 dp[1][5] 就是标准答案.

CPP 代码奉上:

上面的有些版本编译器不通过。

Hello world!
文章已创建 197

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部