在C#版发一个石子合并问题，看看大家对这类问题的一般思路是什么！
这是一个小问题，不算难，却有不少大牛甚至大师都研究过这个问题

n堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。试设计一个算法，计算出将n堆石子合并成一堆的最小代价。

举个例子，比如： 1 2 3 4，有不少合并方法，比如

1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19) 
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24) 
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价

可以看出，第一种方法的代价最低，现在随便给出n堆石子，用程序算出这个最小合并代价

------解决方案--------------------
总是从n堆石子中找出相邻的两堆，要求其和最小，将其合并为一堆，

然后重复前面的过程！
------解决方案--------------------
有意思。。。。

是否可以 这样【思路】：

随便给出N堆石子 每堆石子数不定

然后先对石子堆按每堆石子数排序后再按照帖子中的方案一进行操作？

 这样不就可求出最小代价了么。。。
------解决方案--------------------
好像哈弗曼编码啊
------解决方案--------------------
F[i,j] 表示第i堆到j堆合并的最小代价，那么 F[i,j] = min (F[i,k] + F[k + 1, j] + cost(k,k + 1)), i <= k < j

那么转移为O(n) 总体复杂度O(N^3)
------解决方案--------------------
cost(k, k + 1) 为 i到k堆合并后和 k + 1 到 j 合并后的两堆合并的代价

cost(k, k + 1) = sigma(i...j) = weight[i] + weight[i +1] + ... + weight[j]

sum[i] = sum[1] + sum[2] + ... + sum[i]

则sigma(i...j) = sum[j] - sum[i - 1]

所以在知道sum[i]后计算cost(k, k + 1) 为 O(1)

sum[i]可以预先计算出来，需要O(N) 的时间
------解决方案--------------------
总是从n堆石子中找出相邻的两堆，要求其和最小，将其合并为一堆，

然后重复前面的过程！
------解决方案--------------------
DP + 四边形不等式?
------解决方案--------------------
可以乱序应该就退化成贪心哈夫曼编码了
------解决方案--------------------
谈谈一般的解题思路。

在N比较小的情况下，可以求得最优解。

然后提出各种近似最优解的算法，拟合。
（目前能想到的近似算法：astar/启发，动态规划，贪心、蒙特卡洛抽样……）

再代入N比较大的环境里面检验。讨论解的优越性，算法复杂度，最好/最糟糕情况。
------解决方案--------------------
我就分析一下：
就以4个数为例：
最后的结果，有几个数。
其中一个就是四个数的和，而另外几个数就是：
四个数中的两两之和。
比如1 2 3 4.
必须要加的数是 10
然后在里面选择最小的两数 1 2 相加得3
现在就是 3 3 4 再选出最小的数 3 3相加得6 现在总复杂度为9
最后加10 得出19
所以，简单一点的算法就是，每次找出其中的最小两数合并。
感觉就像是用树编码，要得出最优结果就得让大数靠近树根，小数不远离树根。
------解决方案--------------------
每次的代价=这个数列总和-余下的数列和
余下的数列的和大，代价就小
如果不取小的，取相对较大的得到的新的数列的最小代价会大于等于原数列的最小代价
------解决方案--------------------
排序 最小查找长度

------解决方案--------------------
动态规划思想``

max{f(x,i)+f(i+1,y),x<i<y} y-x>1
f(x,y)= 
x+y y-x=1


问题答案为 f(1,n)
------解决方案--------------------

探讨

给你断贴。

有空给大家写一个穷举获得最优解的程序。

然后找找规律

------解决方案--------------------
每次合并将相邻堆和最小的合并，合并n-1次
------解决方案--------------------
给出我的思路……

找出相邻的两个数和最小的值，相加后得到一个新的N个堆，从这N个堆中在找出相邻的和最小的两个值
------解决方案--------------------
亲爱的，你看我的代码写的美吗？

C# code

using System;
namespace ConsoleApplication5
{
    class Program
    {
        static int MinCost = int.MaxValue;
        static string MergeHistory = "";
        static int[] Stones = new int[] { 1, 2, 3, 4 };
        static void Main(string[] args)
        {
            //典型的回朔问题。
            Merge(0, 0, "");
            Console.Write("操作步骤：" + MergeHistory + "最小值：" + MinCost);
            Console.Read();
        }

        static void Merge(int i, int Cost, string History)
        {
            if (i == Stones.Length - 1)
            {
                //结束,比较最小花费。
                if (MinCost > Cost)
                {
                    MinCost = Cost;
                    MergeHistory = History;
                }
            }
            else
            {
                History += "合并" + Stones[i] + "和" + Stones[i + 1] + "=";
                Stones[i + 1] += Stones[i];//搬过去
                Merge(i + 1, Cost + Stones[i + 1], History + Stones[i + 1] + ";");
                Stones[i + 1] -= Stones[i];//再拿回来,回朔                 
            }
        }
    }
}