回答你的主要问题:重叠子问题和最优子结构都是不同的概念/属性,同时满足这些属性或条件的问题可以通过动态规划来解决。要理解它们之间的区别,您实际上需要了解每个术语对于动态规划的含义。
我了解这两种方法的目标方法,其中最优子结构根据输入 n 计算最优解决方案,而重叠子问题则针对输入范围(例如从 1 到 n)的所有解决方案。
这是一个措辞不佳的声明。您需要熟悉动态规划的基础知识。希望以下解释能够帮助您入门。
让我们首先定义这些术语“最佳子结构”和“重叠子问题”的含义。
最优子结构:如果大小为 n 的问题的最佳解决方案 S 可以通过以下方式计算JUST查看子问题 s 的最优解,其大小 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 & 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) 存储在table第一次遇到之后,下次再遇到的时候就不需要再重新计算了。我们可以重用存储的结果,从而节省大量计算量。
当我们实现迭代解决方案时,“表”通常是一个数组(或数组的数组),当我们实现递归解决方案时,“表”通常是一个动态数据结构,一个哈希图(字典)。
您可以进一步阅读this https://stackoverflow.com/questions/1065433/what-is-dynamic-programming链接以更好地理解这两种方法。