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

Question

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

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

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

编辑：这个标准实际上是在著名的书：动态编程章节中的 CLRS 算法介绍中给出的。

Answer 1

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

我通常看到独立的子问题作为分治式算法的标准给出，而我看到重叠的子问题和最优子结构作为动态规划系列的标准给出。（直观上，最优子结构是指一个较大问题的最佳解由子问题的最佳解组成。经典的例子是图问题中的最短路径：如果知道从A到B的最短路径经过C，那么你也知道从A到B的最短路径中经过C的部分恰好是从A到C的最短路径。）

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

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

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