algorithm - 应用动态规划技术的子问题的独立性

Question

通过动态规划技术解决算法的两个标准是

1. 子问题应该是独立的。
2. 子问题应该重叠。

我想我明白重叠的意思了。它基本上意味着子问题具有可能相同的子子问题。因此，我们不是一遍又一遍地解决子子问题，而是解决它一次，将它放在哈希表或数组中，并可以在需要的时候查找它。但是第 1 点，即子问题的独立性在这里是什么意思？如果它们有一些共同的子子问题，我们如何称它们为独立的？我的意思是，在这个阶段，这对我来说听起来非常违反直觉。

编辑:这个标准实际上是given in the famous book: Introduction to Algorithms by CLRS in the Dynamic Programming chapter.

Answer 1

请告诉我们您在哪里读到 DP 适用于具有重叠和独立子问题的问题。我认为这是不正确的，出于与您给出的相同的直觉原因——如果问题重叠，它们就不是独立的。

我通常将独立的子问题作为分而治之风格算法的标准，而我将重叠子问题和最优子结构作为动态规划系列的标准. (直观上，最优子结构是指一个更大问题的最优解是由子问题的最优解码成的。经典的例子是图问题中的最短路径:如果知道从A到B的最短路径经过C，那么你也知道从 A 到 B 的最短路径中经过 C 的 部分恰好是从 A 到 C 的最短路径。)

更新:哦，我明白了——是的，我猜他们确实提到了独立性。但我没有像你一样强调这一点。意思是，他们提到独立性是在更大、更重要的最优子结构概念的背景下，或者作为一种理解方式。

他们所说的独立性具体指的是，即使两个问题重叠，它们在不相互作用的意义上是“独立的”——一个问题的解决方案并不真正依赖于另一个问题的解决方案。他们实际上使用了我所做的相同示例，即最短路径。最短路径问题的子问题是独立的更小的最短路径问题:如果从 A 到 B 的最短路径经过 C，那么从 A 到 C 的最短路径不使用从 C 到最短路径中的任何边B. 相比之下，最长路径 问题不具有子问题的独立性。

我不认为 CLRS 提出独立性是错误的，但我确实认为他们使用的语言有点模棱两可。