algorithm - 动态规划和分而治之

Question

我正在阅读 notes on Dynamic programming ，我遇到了以下评论。

If the subproblems are not independent, i.e. subproblems share subsubproblems, then a divideand-conquer algorithm repeatedly solves the common subsubproblems. Thus, it does more work than necessary

这是什么意思？您能否举例说明上述观点？

Answer 1

作者提到了这样一个事实，即许多分而治之的算法都有相互重叠的子问题。例如，考虑这个非常简单的 Fibonacci 实现:

int Fibonacci(int n) {
    if (n <= 1) return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

如果您跟踪为计算 Fibonacci(4) 所做的调用，我们得到

• Fibonacci(4) 调用 Fibonacci(3) 和 Fibonacci(2)
• Fibonacci(3) 调用 Fibonacci(2) 和 Fibonacci(1)
• Fibonacci(2) 调用 Fibonacci(1) 和 Fibonacci(0)
• Fibonacci(2)(另一个)调用 Fibonacci(1) 和 Fibonacci(0)
• Fibonacci(1) 终止。
• Fibonacci(1) 终止。
• Fibonacci(1) 终止。
• Fibonacci(0) 终止。
• Fibonacci(0) 终止。

换句话说，总共进行了 9 次函​​数调用，但这里只有 5 次不同的调用(0 到 4 的斐波那契数列，包括在内)。如果递归调用在子问题之间共享而不是每次都从头开始重新计算，则可以使该算法更加高效。这是动态规划背后的关键思想之一。

为了计算 F_n(第 n 个斐波那契数)，上面的代码将总共进行 2F_n+1 - 1 次递归调用。由于 Fibonacci 数呈指数级快速增长，因此这需要呈指数级的大量工作。但是，可以利用许多递归调用相同的事实来显着简化这一过程。让我们从 Fibonacci(0) 开始向上计算，而不是从 Fibonacci(4) 开始向下计算。具体来说，我们将构建一个长度为 5 的表(我们称之为 FTable)，并按如下方式填充:

• FTable[0] = 0
• FTable[1] = 1

现在，假设我们要计算 FTable[2]。这要求我们知道 FTable[0] 和 FTable[1]，但我们已经知道了，因为它们在表中。因此我们可以设置

• FTable[2] = 1

使用类似的逻辑，我们可以从 FTable[2] 和 FTable[1] 计算出 FTable[3]:

• FTable[3] = 2

FTable[4] 来自 FTable[2] 和 FTable[3]:

• FTable[4] = 3

请注意我们是如何通过以相反的顺序构建它们来避免进行大量重叠的递归调用的!这现在在时间 O(n) 中计算斐波那契数，这比以前快了指数级。使用一些更高级的数学，我们可以做得比这更好，但这确实说明了为什么动态规划可以将不可行的问题突然变成可行的。

希望这对您有所帮助!