这类问题是动态规划中经典题型，主要有三种变形。网上关于这个问题的资料很多，我就不赘述了。简单的介绍一下这三种题型。
有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。 这类问题使用贪心算法即可解决，哈夫曼树的变形。每次只要合并最小的两堆，即可保证结果最小（最大）。
链式结构：有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。 这个问题需要使用动态规划求解，如果使用贪心算法求得当前最小值可能不是最优解。如： 7 6 5 7 100 如果使用贪心算法，合并思路为6+5 =11；7+11 =18；18+7 = 25；25+100 = 125。正确的最优解应该是通过动态规划求得：7+6 = 13；5+7 = 12；13+ 12 = 25; 25+100 = 125; 最后结果应该是13+12+25+125 = 175。
环形结构：在一个圆形操场的四周有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。
设dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式：
#include "stdafx.h" #include <iostream> #include <vector> #include <climits> #include <iomanip> using namespace std; int movebook_list(vector<int> book){ int length = book.size(); if (length == 0) return 0; if (length == 1) return book[0]; int mergeTotal = INT_MAX; int **dp = new int *[length];//保存i->j合并的最优结果 int **s = new int *[length];//保存截断点位置 int **sum = new int *[length];//保存i-j的和 for (int i = 0; i < length; i++){ dp[i] = new int[length]; s[i] = new int[length]; sum[i] = new int[length]; } for (int i = 0; i < length; i++){ dp[i][i] = 0; s[i][i] = i; sum[i][i] = book[i]; for (int j = i + 1; j < length; j++){ sum[i][j] = sum[i][j-1] + book[j]; } } for (int len = 2; len <= length; len++) { int j; for (int i = 0; i < length - len + 1; i++) { j = (i + len - 1) ; dp[i][j] = INT_MAX; for (int k = s[i][j-1]; k<=s[i+1][j]&& (k<j);k++)//利用四边形法则进行优化，添加一个截断的标志位s，后面的求解根据之前截断点继续向后搜索以简化求解过程 { if (dp[i][j]> dp[i][k] + dp[k+1][j] + sum[i][j]){ dp[i][j] = dp[i][k] + dp[k+1][j] + sum[i][j]; s[i][j] = k; } } } } mergeTotal = dp[0][length - 1]; //打印求解所使用的矩阵 for (size_t i = 0; i < length; i++) { int j = 0; for (; j < i; j++) cout << setw(4) << ""; for (; j < length; j++) cout << setw(4) << left << sum[i][j]; cout << endl; } cout << endl; for (size_t i = 0; i < length; i++) { int j = 0; for (; j < i; j++) cout << setw(4) << ""; for (; j < length; j++) cout << setw(4) << left << dp[i][j]; cout << endl ; } cout << endl; for (size_t i = 0; i < length; i++) { int j = 0; for (; j < i; j++) cout << setw(4) << ""; for (; j < length; j++) cout << setw(4) << left << s[i][j]; cout << endl; } cout << endl; for (int i = 0; i < length; i++) { delete[] dp[i]; delete[] sum[i]; delete[] s[i]; } delete[] dp; delete[] sum; delete[] s; return mergeTotal; } int main() { int N = 0; vector <int> b = { 7,6,5,7,100}; while (cin >> N){ cout << movebook_list(b); cout << endl; } return 0; }状态转移公式：
i<=k<j int movebook_circle(vector<int> book){ int length = book.size(); if (length == 0) return 0; if (length == 1) return book[0]; int mergeTotal = INT_MAX; int **dp = new int *[length]; int **s = new int *[length]; int **sum = new int *[length]; for (int i = 0; i < length; i++){ dp[i] = new int[length]; s[i] = new int[length]; sum[i] = new int[length]; } for (int i = 0; i < length; i++){ dp[i][i] = 0; s[i][i] = i; sum[i][i] = book[i]; for (int j = i + 1; j < length + i; j++){ sum[i][j%length] = sum[i][(j - 1) % length] + book[j%length]; } } for (int len = 2; len <= length; len++) { int j; for (int i = 0; i < length; i++) { j = (i + len - 1) % length; dp[i][j] = INT_MAX; for (int k = i; k<i + len - 1; k++) { if (dp[i][j]> dp[i][k%length] + dp[(k + 1) % length][j] + sum[i][j]) dp[i][j] = dp[i][k%length] + dp[(k + 1) % length][j] + sum[i][j]; } } } for (int j = 0; j < length; j++) { if (dp[(j + 1) % length][j] < mergeTotal) mergeTotal = dp[(j + 1) % length][j]; } for (size_t i = 0; i < length; i++) { int j = 0; for (; j < length; j++) cout << setw(4) << left << sum[i][j]; cout << endl; } cout << endl; for (size_t i = 0; i < length; i++) { int j = 0; for (; j < length; j++) cout << setw(4) << left << dp[i][j]; cout << endl; } cout << endl; for (int i = 0; i < length; i++) { delete[] dp[i]; delete[] sum[i]; delete[] s[i]; } delete[] dp; delete[] sum; delete[] s; return mergeTotal; } int main() { int N = 0; vector <int> b = { 7,6,5,7,100}; while (cin >> N){ //cout << movebook_list(b); //cout << endl; cout << movebook_circle(b); cout << endl; } return 0; }
