algorithm - 动态规划：最优二叉搜索树和霍夫曼

Question

是否可以通过贪心算法而不是动态规划（DP）（例如霍夫曼算法）来构建最佳二叉搜索树（OBST）？如果是这样，为什么在构建 OBST 时首选 DP？

Answer 1

没有有效的贪心算法来总是构造一个最优的二叉搜索树。然而，可能存在启发式算法，例如构造接近最优树的贪心算法，这在实践中可能更可取。