动态规划比递归要复杂很多，为了让自己不忘记，还是决定在这个程序中将思考过程写一下，因为发现动态规划类的思考过程其实大同小异。
问题分析
操场玩法情况下 假设有6堆石子，数量分为3，4，6，5，4，2
最初想到用贪心算法思想去看
2+3=5
5+4=9
5+4=9
9+6=15
15+9=24
总计算量=5+9+9+15+24=62
看上去挺完美的，哈哈
接下来就是神奇的地方：
3+4=7
7+6=13
4+2=6
5+6=11
13+11=24
总计算量=7+13+6+11+24=61
贪心算法的本质是得到局部最优，而不能保证全局最优这里理解局部最优和全部最优很关键
1.分析最优解的结构特征
假设我们已经知道前K堆石子合并，后n-k堆石子合并能得到最优解，那么原问题就变成了两个子问题求最优解。
假设已经知道n堆石子合并的最优计算总量为c，子问题{ai……ak}的计算总量为a,子问题{ak……an}的计算总量为b,i到n的石子数量和为w(i,n),那么c=a+b+w(i,n). 如果c是最优的，那么a和b一定是最优的。也就是所原问题的最优解包含的子问题最优解。
2.建立最优值递归式
设Min[i,j]表示i-j堆石子合并的最小计算量，Min[i,k]表示i-k堆石子合并的最小计算量,Min[k+1,j]表示k-j堆石子合并的最小计算量
0 ,i=j
Min[i,j]={Math.Min(Min[i,k]+Min[k+1,j]+w(i,j)) ,i<j
同理：
设Max[i,j]表示i-j堆石子合并的最小计算量，Max[i,k]表示i-k堆石子合并的最小计算量,Max[k+1,j]表示k-j堆石子合并的最小计算量
0 ,i=j
Max[i,j]={Math.Max(Max[i,k]+Max[k+1,j]+w(i,j)) ,i<j
using System;using System.Collections.Generic;namespace 石子合并{class Program{public static int Count = 6; //表示小石子的堆数public static readonly int INF = 999999; //不可到达值public static List<int> M = new List<int>();//用于储存每堆小石子的数量public static List<int> S = new List<int>(); //用于储存前n堆小石子的数量//这边如果只是路边玩法 数组大小只需要Count就行 不需要乘2public static int[,] Min = new int[2 * Count, 2 * Count];//用于存放第i到j堆小石子合并的最小计算量public static int[,] Max = new int[2 * Count, 2 * Count];//用于存放第i到j堆小石子合并的最大计算量public static int Min_Cir = 0, Max_Cir = 0;static void Main(string[] args){//随机生成6个1-30的整数表示每堆小石子的数量//并将结果放入M和S两个数组int s = 0;S.Add(s);Random random = new Random();for (int i = 0; i < Count; i++){int x = random.Next(1, 30);s += x;M.Add(x);S.Add(s);}Console.Write("小石子的堆数分别是：");foreach (var v in M)Console.Write(v + " ");Console.WriteLine();RoadPlay();Console.WriteLine("路边玩法最小花费为：" + Min[0, Count - 1]);Console.WriteLine("路边玩法最大花费为：" + Max[0, Count - 1]);CircularPlay();Console.WriteLine("环形玩法最小花费为：" + Min_Cir);Console.WriteLine("环形玩法最大花费为：" + Max_Cir);Console.ReadKey();}static void RoadPlay(){//初始化结果矩阵for (int i = 0; i < Count; i++){Min[i, i] = 0;Max[i, i] = 0;}for (int z = 2; z <= Count; z++)//合并小石子的堆数{for (int i = 0; i <= Count - z; i++) //i表示合并小石子堆的起点{int j = z + i - 1; //j表示合并小石子堆的终点Min[i, j] = INF;Max[i, j] = -1;int temp = S[j + 1] - S[i];//记录i至j之间小石子数之和for (int k = i; k < j; k++) //i至j中间点{Min[i, j] = Math.Min(Min[i, j], Min[i, k] + Min[k + 1, j] + temp);Max[i, j] = Math.Max(Max[i, j], Max[i, k] + Max[k + 1, j] + temp);}}}}/// <summary>/// 环形玩法可以转换为直线玩法///将环看成长度为2*n-1的直线来处理/// </summary>static void CircularPlay(){for (int i = 0; i < Count - 1; i++){M.Add(M[i]);S.Add(S[Count + i] + M[i]);}Count = 2 * Count - 1;RoadPlay();Count = (Count + 1) / 2;//找最优解Min_Cir = Min[0, Count - 1];Max_Cir = Max[0, Count - 1];for (int i = 1; i < Count; i++){if (Min[i, i + Count - 1] < Min_Cir)Min_Cir = Min[i, i + Count - 1];if (Max[i, i + Count - 1] > Max_Cir)Max_Cir = Max[i, i + Count - 1];}}}}
