如何证明这个贪心算法是最优的：杆连接
how to prove this greedy algorithm as optimal: rod connection
这是问题所在：
给定一个数组表示 table 上杆的长度。每次选择两根杆并将它们连接起来并获得一根新杆。这样做直到 table 上只有一根杆。
连接的成本是两根杆的长度之和，例如，连接 2 和 3 将得到 5 根杆，成本为 5。
什么是最低成本连接策略？
贪心：每次挑最短的两个，把连接好的新杆放回table。
示例：
[1,2,3,4,5] ，选择 1 和 2 花费 3 [3,3,4,5]，选择 3 和 3 花费 6 [4,5,6]，选择 4 和5花费9[6,9]，挑6和9花费15。所以总花费是33。
不能简单的说，总的连接次数是n-1次，所以每次都取最小的两个，最后的cost最小。因为每一次挑都会改变未来，像挑1+2和挑2+4都会导致下一步的两套不同的竿。
我如何证明这种贪婪会得到最低成本？
证明类似于霍夫曼编码最优的证明。
每个策略对应一个二叉树。它包含其叶子中的所有初始杆，内部顶点对应于连接操作。
可以看出，固定树的连接杆的成本是a[v] * depth[v]所有叶子v的总和，其中a[v]是初始杆的长度depth[v] 是休假的深度。之所以如此，是因为每根杆恰好参与了一次连接 depth[v] 次。
我们需要证明存在一个最优策略使得它的树有两个最短的杆作为兄弟姐妹。
假设 T 是一棵最优树。让我们按深度对它的叶子进行排序（按非严格递减顺序）。如果最短的两根杆是前两片叶子，我们就完成了。否则，让我们继续将它们与它们的左兄弟（至少与它们一样长）交换，直到它们进入前两个位置。当我们交换 2 个叶子 u 和 v 时，成本变化是 -depth[u] * a[u] - depth[v] * a[v] + depth[u] * a[v] + depth[v] * a[u] = (depth[v] - depth[u]) * (a[u] - a[v])。第一项是非正数（因为叶子按高度排序），第二项是非负数（如 a[u] >= a[v]）。因此，成本变化为负或零。
因此，存在一棵最优树，其中两个最短的杆是兄弟姐妹。这意味着有一个最佳策略，我们在做任何其他事情之前将这两根杆连接起来。
这是问题所在：
给定一个数组表示 table 上杆的长度。每次选择两根杆并将它们连接起来并获得一根新杆。这样做直到 table 上只有一根杆。 连接的成本是两根杆的长度之和，例如，连接 2 和 3 将得到 5 根杆，成本为 5。 什么是最低成本连接策略？
贪心：每次挑最短的两个，把连接好的新杆放回table。
示例：
[1,2,3,4,5] ，选择 1 和 2 花费 3 [3,3,4,5]，选择 3 和 3 花费 6 [4,5,6]，选择 4 和5花费9[6,9]，挑6和9花费15。所以总花费是33。
不能简单的说，总的连接次数是n-1次，所以每次都取最小的两个，最后的cost最小。因为每一次挑都会改变未来，像挑1+2和挑2+4都会导致下一步的两套不同的竿。
我如何证明这种贪婪会得到最低成本？
证明类似于霍夫曼编码最优的证明。
每个策略对应一个二叉树。它包含其叶子中的所有初始杆，内部顶点对应于连接操作。
可以看出，固定树的连接杆的成本是a[v] * depth[v]所有叶子v的总和，其中a[v]是初始杆的长度depth[v] 是休假的深度。之所以如此，是因为每根杆恰好参与了一次连接 depth[v] 次。
我们需要证明存在一个最优策略使得它的树有两个最短的杆作为兄弟姐妹。
假设 T 是一棵最优树。让我们按深度对它的叶子进行排序（按非严格递减顺序）。如果最短的两根杆是前两片叶子，我们就完成了。否则，让我们继续将它们与它们的左兄弟（至少与它们一样长）交换，直到它们进入前两个位置。当我们交换 2 个叶子 u 和 v 时，成本变化是 -depth[u] * a[u] - depth[v] * a[v] + depth[u] * a[v] + depth[v] * a[u] = (depth[v] - depth[u]) * (a[u] - a[v])。第一项是非正数（因为叶子按高度排序），第二项是非负数（如 a[u] >= a[v]）。因此，成本变化为负或零。
因此，存在一棵最优树，其中两个最短的杆是兄弟姐妹。这意味着有一个最佳策略，我们在做任何其他事情之前将这两根杆连接起来。