重叠子问题和最优子结构有什么区别？

Question

我理解这两种方法的目标方法，其中最优子结构基于输入n计算最优解，而重叠子问题针对输入范围从1到n的所有解。

对于像棒切割问题这样的问题。在这种情况下，在寻找最佳切割时，我们是否考虑每个切割，因此可以将其视为重叠子问题，并自下而上进行工作。或者，我们考虑给定输入n的最优切割，并自上而下地工作。

因此，虽然它们最终处理的是最优性，但这两种方法之间的确切区别是什么。

我试着参考这个重叠的子问题，最优子结构和这一页。

另外，这与制表（自上而下）和记忆（自下而上）的求解方法有关吗？

这条线索说明了一个有效的观点，但我希望它能更容易地被分解。

Answer 1

为了回答你的主要问题：重叠子问题和最优子结构都是不同的概念/属性，一个同时满足这些属性或条件的问题可以通过动态规划来解决。要理解它们之间的区别，你实际上需要理解这些术语在动态规划方面的含义。

我理解这两种方法的目标方法，其中最优子结构基于输入n计算最优解，而重叠子问题针对输入范围从1到n的所有解。

这是一个措辞不当的声明。您需要熟悉动态编程的基础知识。希望下面的解释能帮助你开始。

让我们从定义这些术语中的每一个开始，最优子结构

最优子结构：如果一个问题的最优解，大小为n，可以通过查看子问题的最优解来计算，大小为s

示例（最短路径问题）：考虑一个无向图，其顶点为 a，b，c，d，e 和边 （a，b）、（a，e）、（b，c）、（c，d）、（d，a）

• a -- b （最短路径）
• a -- e -- b

最长路径问题没有最优子结构。之间的最长路径

重叠的子问题:如果你从你分享的链接看这个图:

您可以看到子问题fib（1）是跨多个分支的“重叠”，因此fib（5）具有重叠的子问题（fib（1）、fib（2）等）。

另外，这与制表（自上而下）和记忆（自下而上）的求解方法有关吗？

这又是一个措辞拙劣的问题。自上而下（递归）和自下而上（迭代）方法是使用记忆解决DP问题的不同方法。摘自维基百科关于记忆的文章：

在计算中，记忆或记忆是一种优化技术，主要用于通过存储昂贵的函数调用的结果并在再次出现相同的输入时返回缓存结果来加速计算机程序。

对于给定的斐波那契示例，如果我们在第一次遇到 fib（1） 后将其存储在表中，则下次看到它时不需要再次重新计算它。我们可以重用存储的结果，从而节省大量的计算。

当我们实现迭代解决方案时，“表”通常是一个数组(或数组的数组)，当我们实现递归解决方案时，“表”通常是一个动态数据结构，一个hashmap(字典)。

您可以进一步阅读此链接，以便更好地理解这两种方法。