dynamic - 最佳子结构的直觉是什么？

Question

这个问题与动态规划有关，特别是来自 CLRS Pg 362 的棒切割问题

整体最优解包含两个相关子问题的最优解。

通过找到单个子问题的最优解，然后以某种方式将它们组合在一起，从而获得整体最优解。我无法理解直觉和概念。任何链接，示例？

谢谢

Answer 1

您可以比较动态编程和贪婪方法。

最优子结构是指通过找到子问题的最优解可以找到最优解。如果不是这种情况，那么子问题的最优解之和不会给我们最优的全局解。

例如，考虑 Dijkstra 算法。如果我们知道从节点 A 到节点 C 的最短路径，那么我们也可以使用此信息来找到到另一个节点的最短路径。

如果不是这种情况，我们就无法对子问题组合最优解并获得全局最优解，我们可以使用贪心方法。例如，看看改变问题。贪心算法做出局部最优决策并找到一些解决方案，但不能保证该解决方案是最优的。