这是在某本竞赛书上看到的 一个比较简单的贪心算法题。
书上采用了二叉树模型形象地呈现切割过程：
然后给出了这么一句话：
(然后就开始哗啦哗啦写代码了）
冥冥之中还是能感受出这句话的合理之处。。。
但是许多初步接触贪心算法的萌新可能突然就懵了：“兄弟。。节点···？为什么啊！兄dei！？。
这里提供一个易于理解的思路：
细心思考你就会发现，当切割结果确定后，切割次数就确定了，所以说这个问题的本质就是如何调整切割策略，使得每次切割花费总和最小。。。
不如咱们反过来想这个问题！
它就变成了：有一堆切好的木板，每一次拼装和和切割的花费一致，如何确定拼装策略，使得总花费和最小。
看似并没有改变什么本质的东西，但是它让你更接近对上图中最优切割的性质的理解。假如我们要拼装的话，既然总的拼装次数是一定的，那我们就尽量想办法让每一次的拼装操作花费最小（谈心的精髓思想） 。考虑到每一次拼装的花费=所拼装的两块木板长度和，那我们每一次拼装就尽量选取所有木板段子中最小的两个拼。于是咱们把这个拼装过程从下往上整合成二叉树，反过来从上到下就得到了最优分割策略的二叉树。
——于是！对于最优切割性质中“最短板是深度最大的子节点之一”和“最短板与次短板应当是兄弟节点”的阐述就豁然开朗了！
.
.
.
......了吧..
原文：https://www.cnblogs.com/fighlone/p/12977755.html