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

Question

我了解两种方法的目标方法，其中最优子结构根据输入 n 计算最优解，而重叠子问题针对输入范围内的所有解，比如从 1 到 n。

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

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

我尝试参考这个重叠子问题、最优子结构和这个页面。

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

这个线程提出了一个有效的观点，但我希望它可以更容易地分解。

Answer 1

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

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

这是一个措辞不佳的声明。您需要熟悉动态规划的基础知识。希望以下说明可以帮助您入门。

让我们首先定义这些术语，最优子结构和重叠子问题的含义。

最优子：如果一个问题，S，大小为N最佳的解决方案可以计算JUST寻找一个子问题的最佳解决方案，S，大小为<n和不是所有的解决方案，以子问题，和它也将导致最佳的解决方案对于问题 S，则认为该问题 S 具有最优子结构。

示例（最短路径问题）：考虑具有顶点 a,b,c,d,e 和边 (a,b), (a,e), (b,c), (c,d), (d) 的无向图,a) & (e,b) 那么 a & c 之间的最短路径是 a -- b -- c 这个问题可以分解为找到 a & b 之间的最短路径，然后找到 b & c 之间的最短路径，这将给我们一个有效的解决方案。请注意，我们有两种从 a 到达 b 的方法：

• a -- b (最短路径)
• a--e--b

最长路径问题没有最优子结构。a & d 之间的最长路径是 a -- e -- b -- c -- d，但是 a & c (a -- e -- b -- c) 和 c & d (c -- b -- e -- a -- d) 不会给我们一个有效的（非重复顶点）a & d 之间的最长路径。

重叠子问题：如果您从共享的链接中查看此图：

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

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

这又是一个措辞不佳的问题。自顶向下（递归）和自底向上（迭代）方法是使用记忆化解决 DP 问题的不同方法。来自维基百科 Memoization 文章：

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

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

当我们实现迭代解决方案时，“表”通常是一个数组（或数组数组），而当我们实现递归解决方案时，“表”通常是一个动态数据结构，一个哈希图（字典）。

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