在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)
[解决办法]
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];//再拿回来,回朔 } } }}
[解决办法]
to:hit_cold
少了两行代码，急于下班，没有耐心。
明天再找时间改成非递归，因为堆栈可能会溢出。
改成非克隆的，估计还可以优化。
可能还可以利用链表。因为涉及到移除一个节点，还原这个节点之类的。
可能有序数字规律上还可以优化，因为有序，也许可以利用二分，二叉之类的。
如果不保存操作步骤，只要最小代价，可能会节省大量内存开销。
3000的时候，他说0.6秒。
太晚了，上来看一眼，稍做修改，明天再说。
using System;using System.Collections.Generic;using System.Diagnostics.PerformanceData;namespace ConsoleApplication4{ class Program { static int MinCost = int.MaxValue; static string MergeHistory = ""; static void Main(string[] args) { //典型的回朔问题。 System.Diagnostics.Stopwatch Sw = new System.Diagnostics.Stopwatch(); Sw.Reset(); List<int> Stones = new List<int>(); for (int i = 1; i < 3000; i++) { Stones.Add(i); } try { Sw.Start(); Merge(Stones, 0, ""); Sw.Stop(); } catch { } Console.WriteLine("操作步骤：" + MergeHistory + "最小值：" + MinCost); Console.WriteLine("操作用时：" + Sw.Elapsed.TotalSeconds + "秒"); Console.Read(); } static void Merge(List<int> Stones, int Cost, string History) { if (Stones.Count == 1) { //结束,比较最小花费。 if (MinCost > Cost) { MinCost = Cost; MergeHistory = History; } } else { int minCost = int.MaxValue; int i = 0; for (int j = 0; j < Stones.Count - 1; j++) { if (minCost < Cost + Stones[j] + Stones[j + 1]) { i = j; minCost = Cost + Stones[j] + Stones[j + 1]; if (Stones[j] + Stones[j + 1] > minCost) { break; } } } List<int> newStones = new List<int>(Stones); newStones[i + 1] += newStones[i]; newStones.RemoveAt(i); Merge(newStones, Cost + Stones[i] + Stones[i + 1], History + "合并" + Stones[i] + "和" + Stones[i + 1] + "=" + (Stones[i] + Stones[i + 1]) + ";"); } } }}
[解决办法]
个人觉得最好的方法是找出i位置，令start->i的累加和i->end的累加最接近。以i为分割点。
同样方式处理分出来的两数组。
测试了一下，速度可以。可惜没时间把递归修改一下。代码其实很简单，就不拷了。
[解决办法]
不知道，你听没听说过“进化算法”，这种算法的实现完全靠随机的蛮力对抗穷举的可能性。
我举一个简单的例子1234：
这4个数里面1无疑是最小的，那么从1出发，可以有1+2；
第二小的是2，从2出发可以有2+1和2+3；
然后是3，有3+2和3+4；
最后是4，有4+3。
这是第一轮
第二轮，
如果继续从1开始，那么1+2之后是334；
如果从2开始，那么可以有334和154；
如果从3开始，那么可以有127和154；
如果从4开始，可以有127；
然后继续下一轮；
第三轮的时候：
如果从1开始，那么可以有64和37；
从2开始，可以有(64和37)以及(64和19)；
从3开始，可以有(37和19)以及(19和64)；
从4开始，可以有19和37；
然后继续往下算，可能n小的情况下，无法看出优劣。
这个算法就像进化，算的时候淘汰掉对最后结果的不利因素，
保留对最后结果的有利因素，最终进化到最有利的结果。
[解决办法]
发一个用于验证的程序，用穷举但缓存优化。
1000个正整数大概花20秒
class Program{ static void Main(string[] args) { Random random = new Random(1); int[] array = Enumerable.Range(0, 1000).Select(t => random.Next(1, 100)).ToArray(); Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); { int mergeCost = CalcMinimalMergeCost(array); } stopwatch.Stop(); Console.WriteLine(stopwatch.Elapsed); } public static int CalcMinimalMergeCost(int[] array) { int dummy; MergeCostLookup.Clear(); return MinMergeCost2(array, 0, array.Length - 1, out dummy); } private static Dictionary<int, int> MergeCostLookup = new Dictionary<int, int>(); private static int MinMergeCost2(int[] array, int start, int end, out int weight) { // trivial cases (1 to 3 elements) switch (end - start) { case 0: weight = array[start]; return 0; case 1: weight = array[start] + array[end]; return weight; case 2: weight = array[start] + array[end - 1] + array[end]; int costMergeLeft = (array[start] + array[end - 1]) + weight; int costMergeRite = weight + (array[end - 1] + array[end]); return Math.Min(costMergeLeft, costMergeRite); } // try a cache look up weight = 0; int rangeKey = (start << 16) + end; if (MergeCostLookup.ContainsKey(rangeKey)) { return MergeCostLookup[rangeKey]; } // scan all combinations int minCost = int.MaxValue, leftWeight = 0, riteWeight = 0; for (int mid = start; mid < end; mid++) { leftWeight = riteWeight = 0; int costLeft = MinMergeCost2(array, start, mid, out leftWeight); int costRite = MinMergeCost2(array, mid + 1, end, out riteWeight); if (costLeft + costRite < minCost) { minCost = costLeft + costRite; } if(weight == 0 && leftWeight != 0 && riteWeight != 0) weight = leftWeight + riteWeight; } if (weight == 0) { for (int i = start; i <= end; i++) weight += array[i]; } // cache result MergeCostLookup[rangeKey] = minCost + weight; return minCost + weight; }}
[解决办法]
发现一个规律， 谁帮我验证一下。
先求总和的一半。
然后按照 n 把 数组划分为 前后两个部分，确保前后的总和都最接近n
然后最前后递归。
谁帮我验证一下。