algorithm - 贪心算法还是动态规划？

Question

给出了列表 l = [x_1, ..., x_n]。列表中的每个元素都是某 block 木头的长度。要粘合两 block 长度为 a 和 b 的木头，您需要 max(a,b) 的胶水。粘合后，你得到一 block 长度为 a+b 的木头。计算粘合所有部件的最小胶水量。

你认为贪心算法在这里行得通吗？我想不出任何例子。说贪心算法我的意思是:取两 block 最小长度，将它们粘合起来，直到所有 block 都粘合为止。使用一些优先级队列，这可以在 O(n log n) 复杂度内完成。

那有用吗？如果没有，请给我一些列表 l 的例子，它可以用比贪婪算法所说的更少的胶水粘合。

Answer 1

贪心算法并不总是最优的。一个反例是 [1, 2, 2, 3]，贪婪算法将使用 10 个单位的胶水，而最优算法将使用 9 个单位。

贪心算法:

1-2 = 2 glue
2-3 = 3 glue
3-5 = 5 glue
---------------
total = 10 glue

最佳:

2-2 = 2 glue
1-3 = 3 glue
4-4 = 4 glue
--------------
total = 9 glue

它是动态编程。