点击关注公众号，干货第一时间送达
这道题其实挺经典的，
但是，我在力扣上没有找到原题
可能是关键词搜索有问题，
如果有小伙伴找到，
可以私信告诉我
一起来看看。
一、屏幕前的吴彦祖和刘亦菲们，请听题
题目说的稍微有点费解。。。
举个例子：
有多种分割方案：
（1）先分成【40,20】，再分成【10,30,20】，总花费：60+40=100
（2）先分成【10,50】，再分割成【10,20,30】，总花费：60+50=110
（3）先分成【30,30】，再分割成【10,20,30】，总花费60+30=90
最少花费是第三种方案，90
懂了？
怎么求解呢？
二、解题
求解呢，需要用到贪心策略，
我们不能用总长度去尝试分割，
要倒推，
用数组 arr，每次利用最小的两个值，算作一次分割策略，
然后将组成的一块大金条，重新放回数组，排序。
下次还是取最小的两个值。
类似于哈夫曼编码：
每次取最小的两个值，可以利用小根堆自动实现，
将取出的两个值累加，结果再次放回堆中。
依次类推，最后的结果就是最小花费。
看看代码。
完整代码：
public class CodingDemo_03 {
/**
* 分金条的最小花费
* @param arr
* @return
*/
private static int getMinSplitCost(int[] arr){
if (arr == null || arr.length == 0){
return 0;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
minHeap.offer(arr[i]);
}
int ans = 0;
while (minHeap.size() != 1){
int sum = minHeap.poll() + minHeap.poll();
ans += sum;
minHeap.offer(ans);
}
return ans;
}
public static void main(String[] args) {
int[] arr = {10,30,20};
System.out.println(getMinSplitCost(arr));
}
}
输出：
D:\java\bin\java.exe
90
文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
