algorithm - 动态规划和分而治之

Question

我正在阅读有关动态编程的笔记，我遇到了以下评论。

如果子问题不是独立的，即子问题共享子子问题，则分治算法重复解决公共子子问题。因此，它做的工作比必要的多

这是什么意思 ？你能给我举例说明上述观点吗？

Answer 1

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

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)
• 斐波那契(1) 终止。
• 斐波那契(1) 终止。
• 斐波那契(1) 终止。
• 斐波那契(0) 终止。
• 斐波那契(0) 终止。

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

为了计算 F _n（第 n 个斐波那契数），上面的代码将进行总共 2F _n+1 - 1 次递归调用。由于斐波那契数以指数方式快速增长，因此这需要以指数方式进行的大量工作。但是，可以使用许多递归调用相同的事实来显着简化这一点。与其从 Fibonacci(4) 开始向下工作，不如从 Fibonacci(0) 开始向上工作。具体来说，我们将构建一个长度为 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[2] 和 FTable[3] 的 FTable[4]：

• FTable[4] = 3

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

希望这可以帮助！