动态规划之石子合并问题(Circle版)

问题描述

简单说下结果是怎么来的:

43=(4+4) + (4+4+5) + (4+4+5+9)
53=(9+5) + (9+5+4) + (9+5+4+4)

算法分析

这个问题和普通的石子合并问题不同，简单的石子合并问题采用的是将石子线性排列并合并，但是这个问题要求石子按照圆圈排列，所以首尾两个石子是能够合并的。
这就不由得引起我们的思考，我们怎么才能让首尾也相邻呢?
方法有两个：
1.遍历数组的时候将索引从0到2*n之间遍历，但是每次都要%n来求真实索引;
2.直接扩展数组，将两个一模一样的数字连接在一起，然后按照正常索引遍历
OK，明确了这一点我们来分析一下这道题的算法。
首先，这道题要求我们只能将两个相邻的石子合并，许多人看到了这个例子就觉得应该使用贪心法来解决，每次合并最大的两个石子，就可以算出最大值。这是完全错误的，因为这个例子恰好四个石子是有序排列的，所以这个问题不具有局部最优代替整体最优的性质，不能使用贪心法。
但是我们可以发现，这个问题确实具有子问题，子问题就是我们可以选择不同的堆进行合并，例如我们现在要对这四个石子合并，那我们可以选择各种不同的顺序进行合并，上面给的两种极值就是两种不同的合并方法，再比如我们可以(4+4)+(5+9)+(4+4+5+9)=44，即前两个合并，后两个合并，最后一起合并，又是一种不同的方案。
所以我们可以得出结论，问题虽然不具有局部最优代替整体最优的性质，但是其具有各种子问题。那我们自然而然可以想到使用动态规划法来解决这个。
动态规划强调的是状态和选择，所以我们先来分析题目中的状态：
首先状态一定有当前石子的数目，其次就是最后的得分。根据这两个状态我们就可以写出状态转移方程。
在写出状态转移方程之前，我们可以想到另一个题目凸多边形最优三角形剖分问题或者另一个很经典的矩阵连乘问题。这三个题目有一个共同的特点，就是我们都需要寻找分割点，就多个相连的项分开。矩阵连乘我们找的是分割分割矩阵的位置(至少两个矩阵为1组，与本题目两两合并类似)，凸多边形最优三角剖分问题是寻找构成三角形的不同顶点(至少三个1组才能分成一个三角形)。所以本题我们也要参照这两个问题的思路，找出一个分割点。在分割点前的石子合并，在分割点后的石子合并，最后将二块一起合并，听着还很像常见的归并算法(暂时这么理解吧,算法思路是一样的)。
所以我们的状态转移方程也是根据这个分割点来写的，这里只举最小值的例子，最大值是一样的。

Min[i][j]=min(Min[i][j],Min[i][k]+Min[k+1][j]+Sum[j]-Sum[i-1])

逐一解释一下:Min[i][j]表示在i到j这些石子合并得到的最小得分，k为我们的分割点,i<=k<j；Sum[j]表示前j个石子的总和，Sum[j]-Sum[i-1]即为将最后两堆石子合并为最终结果时所得的分数
这么说起来可能有些晦涩，我们看图：

首先看Sum数组，Sum[i]就是当前i个石子的总和,Sum[i]=Sum[i-1]+num[i]。
题中我们需要声明两个二维数组，一个是Min，一个Max(这里声明两个是为了将问题说得更清楚，其实声明一个就足够用了)。一个记录最小值，一个记录最大值。
下面我们来讨论一下数组的遍历顺序问题。从状态转移方程中我们可以看出k>=i恒成立，所以在二维矩阵中我们在计算当前行的M[i][j]时总是需要其下面的某个值(因为用到了Min[k+1][j]，k>=i，所以这个值一定在M[i][j]下面)。所以我们应该从下往上遍历，那么j应该如何遍历呢？
j恒为第i个石子后面的石子(因为需要合并)，所以j应该在i+1到i+n之间遍历。
最终我们从最大值矩阵和最小值矩阵找出整体的最大值和最小值即可。下面来看看代码。

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int Arr[300],Sum[300];
int Min[300][300], Max[300][300];
int main() {
    int n;
    cin >> n;
    // 初始化数组
    for (int i = 1; i <= n; i++) {
        cin >> Arr[i];
        Arr[i + n] = Arr[i];
    }
    // 计算最大和
    for (int i = 1; i <= 2 * n; i++) {
        Sum[i] = Sum[i - 1] + Arr[i];
    }
    // 开始递归循环
    for (int i = 2 * n-1; i >= 1; i--) {
        for (int j = i + 1; j < i + n; j++) {
            Min[i][j] = INF;
            for (int k = i; k < j; k++) {
                //这里相当于在第i堆与第j堆中间选择了第k堆作为中间值,在之前我们已经算好了sum数组
                //Min[i][k]相当于在i,k中间取石子的最小值+M[k+1][j]表示在k+1,j之间取石子的最小值
                //sum[j]-sum[i-1]就表示i-j石子加和
                //为什么要将三者相加呢？
                //我们思考一下i-j是n个元素,n个元素两两合并,只能合并出n-1堆，即算出前n-1堆合并的结果
                //例如石子为4 4 5 9,我们的计算方法应该是4 + (4+4) + (4+4+5) + (4+4+5+9)
                Min[i][j] = min(Min[i][j], Min[i][k] + Min[k + 1][j] + Sum[j] - Sum[i - 1]);
                Max[i][j] = max(Max[i][j], Max[i][k] + Max[k + 1][j] + Sum[j] - Sum[i - 1]);
            }
        }
    }
    // 遍历找到最大与最小值
    int MaxValue = 0, MinValue = INF;
    for (int i = 1; i <= n; i++) {
        MaxValue = max(MaxValue, Max[i][i + n - 1]);
        MinValue = min(MinValue, Min[i][i + n - 1]);
    }
    cout <<"min_value: "<<MinValue << endl << "max_value: "<<MaxValue << endl;
}

总结

石子合并问题是一个蛮有意思的问题，因为它很容易就让人把贪心法和动态规划法弄混。
区分二者很简单，就是看题目是否包含二者的问题性质，贪心法需要具有最优子结构，且具有局部最优代替整体最优的性质。而动态规划算法一定要具最优子结构性质。
其次这个问题和我们之前遇到的凸多边形最优三角剖分和矩阵连乘非常类似。因为它们都是在找子问题、子结构。在不同的位置就问题分开成多个不同的子问题，对这些子问题求最优，然后从将子问题合并得到原问题，不就达到了我们最优子结构的性质了吗。