C++动态规划经典案例解析之合并石子

1. 前言

区间类型问题，指求一个数列中某一段区间的值，包括求和、最值等简单或复杂问题。此类问题也适用于动态规划思想。

如就是极简单的区间问题。如有如下数组：

现给定区间信息，求区间内所有数字相加结果。即求如下图位置数字之和。

Tips： 区间至少包括 个属性，起始端和结束端，求和范围包含左端和右端数字。

直接的解法：

累加数组中 区间的值。

累加数组中区间的值。

将 中的值减去中的值。得到最终结果。

如果对任意区间的求解要求较频繁，会存在大量的重复计算。如分别求区间和之和时，分析可知区间结果等于区间的结果加上的值，或者说区间的值等于的值减。简而言之，只需要求出一个如上两个区间中一个区间的值，另一个区间的值就可得到。

为了减少重复计算，可使用区间缓存理念记录至任意位置的和。

如上的问题便是简单的区间类型问题，解决此类问题的方案称为简单区间类型动态规划。数组也可称为前缀和数组。

编码实现：

有了前缀和数组，计算任意区间数字和的公式为：

如下代码实现，输入任意区间信息，输出区间和信息。

是区间动态规划的极简单应用，下文继续讲解几道典型的区间类型问题。

2. 典型案例

2.1 石子合并

问题描述：

设有堆石子排成一排，其编号为，每堆石子有一定的质量。现在要将这堆石子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

此问题为什么也是区间类型问题？

先看几个样例。如有编号为 堆石子，质量分别为 。则合并方案有如下 种：

合并编号为的石子，合并代价为，再合并新堆和第堆石子，代价为。总代价为。

合并编号为的石子，合并代价为，再合并新堆和第堆石子，代价为。总代价为。

通过上述合并过程，可得到如下有用的结论：

任意相邻两堆石子合并的结果是以这两堆石子的编号作为左、右边界的区间和。如合并编号的石子，代价为区间的和 。合并编号为的石子，结果为区间的和。

无论采用何种合并方案，最后一次合并都是相当于求整个数列的和。

如样例所示，两种合并方案的代价分别为，取最小值再加上所有石子的质量和，即为最后答案。

对于堆的石子，可以随意在中间画出一条分割线，把堆石子抽象成左、右 堆石子（两个区间），根据上述分析，可知最后一次的合并值为这 堆石子的质量总和。

但是，左堆不是真正意义上只有一堆石子，是由许多石子堆组成的一个逻辑整体，有其内部的合并方案，且不止一种，站在宏观的角度，不用关心其内部如何变化，只需关心多种合并方案的最小值是多少。同理，也只需关心右堆最终返回的最佳值。

所以，求解问题可以抽象成：

如果原始问题是一个根问题，则求解左堆或右堆的最佳合并值就是一个子问题，所以，合并石子这道题本质是符合递归特点的。

既然符合递归特点，现在就要考虑如何划分子问题。

绘制如下图递归树，根问题为原始问题，区间划分可以从第一堆石子开始，然后再移动分割线，最后再在多个子问题返回值中取最小值。

Tips： 如果只有一堆石子，则代价为 。

编码实现：

初如化变量。

初始化石子信息和前缀和。

递归实现，子问题是一个区间问题，由左、右分界线确定。

测试。

是否存在重叠子问题？

如下图所示，当石子堆更多时，重叠子问题更多。

使用记忆搜索解决重叠子问题。

递归是由上向下逐步向子问题求助，类似问题也可以采用由下向上的动态规划方案实现。基本思路，每一次合并过程，先两两合并，再三三合并，…最后堆合并。

测试：

2.2 石子合并 II

问题描述：

有 n 堆石子围成一个圈，第 堆石子有 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少?

因为首尾可合并，相比较上述问题，差异在于增加合并的方案。

那么，到底增加了那些合并？

假设石子有 堆，每堆的质量分别为 。

如果考虑环形问题，则任何数字都可以为头、为尾，则会出现如下几种数列。

可以理解，数列变成如下 形式，即将环形变成线性。

动态规划实现：

3. 总结

沉淀过程是一种修行。