动态规划和分而治之

我正在读书动态规划的笔记 http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf，我遇到了以下评论。

如果子问题不是独立的，即 子问题共享子子问题，然后分而治之算法重复解决公共问题 子子问题。 因此，它做了超出必要的工作

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

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

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

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

如果追踪计算 Fibonacci(4) 的调用，我们会得到

• 斐波那契（4）调用斐波那契（3）和斐波那契（2）
• 斐波那契（3）调用斐波那契（2）和斐波那契（1）
• 斐波那契 (2) 调用斐波那契 (1) 和斐波那契 (0)
• Fibonacci(2)（另一个）调用 Fibonacci(1) 和 Fibonacci(0)
• 斐波那契(1) 终止。
• 斐波那契(1) 终止。
• 斐波那契(1) 终止。
• 斐波那契(0) 终止。
• 斐波那契(0) 终止。

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

To compute F_n (the nth Fibonacci number), the above code will make a total of 2F_n+1 - 1 recursive calls. Since the Fibonacci numbers grow exponentially quickly, this requires exponentially much work. However, it's possible to use the fact that many recursive calls are identical to simplify this dramatically. Rather than starting at Fibonacci(4) and working down, let's start at Fibonacci(0) and work up. Specifically, we'll build a table (let's call it FTable) of length 5 and will fill it in as follows:

• FT表[0] = 0
• FT表[1] = 1

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

• FT表[2] = 1

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

• FT表[3] = 2

以及来自 FTable[2] 和 FTable[3] 的 FTable[4]：

• FT表[4] = 3

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

希望这可以帮助！