我了解两种方法的目标方法，其中 Optimal Substructure 根据输入 n 计算最佳解决方案，而 Overlapping Subproblems 针对输入范围(例如从 1 到 n)的所有解决方案。
对于像 Rod Cutting Problem 这样的问题.在这种情况下，在找到最佳切割时，我们是否考虑每个切割，因此可以将其视为重叠子问题并自下而上工作。或者我们是否考虑给定输入 n 的最佳切割并自上而下工作。
因此，虽然他们最终确实处理了最优性，但两种方法之间的确切区别是什么。
我试着引用这个 Overlapping Subproblem , Optimal Substructure和 this page as well .
顺便说一句，这是否与制表(自上而下)和记忆化(自下而上)的解决方法有关？
This thread提出了一个有效的观点，但我希望它是否可以更容易地分解。
最佳答案
回答您的主要问题:重叠子问题和最优子结构都是不同的概念/属性，同时满足这些属性或条件的问题可以通过动态规划来解决。要了解它们之间的区别，您实际上需要了解每个术语在动态规划方面的含义。
I understand the target approach for both the methods where Optimal Substructure calculates the optimal solution based on an input n while Overlapping Subproblems targets all the solutions for the range of input say from 1 to n.
这是一个措辞不佳的声明。您需要熟悉动态编程的基础知识。希望以下说明能帮助您入门。
让我们从定义最优子结构和重叠子问题这些术语的含义开始。
最优子结构:如果问题的最优解 S，大小为 n 可以通过JUST查看子问题的最优解来计算，s，大小为 < n 和 NOT ALL 子问题的解，AND 也会导致问题 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) 等)。
On a side note as well, does this relate to the solving approaches of Tabulation(top-down) and Memoization(bottom-up)?
这又是一个措辞不当的问题。自上而下(递归)和自下而上(迭代)方法是使用记忆化解决 DP 问题的不同方法。来自维基百科的 Memoization 文章:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
对于给定的斐波那契示例，如果我们在第一次遇到 fib(1) 后将其存储在 table 中，则无需再次重新计算当我们下次看到它时。我们可以重复使用存储的结果，从而节省大量计算。
当我们实现迭代解决方案时，“table”通常是一个数组(或数组数组)，而当我们实现递归解决方案时，“table”通常是一个动态数据结构，一个 hashmap(字典)。
您可以进一步阅读 this链接以更好地理解这两种方法。
关于dynamic-programming - 重叠子问题和最优子结构有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58493674/