动态编程和分而治之

Question

我正在读关于动态编程的笔记,我遇到了以下评论.

如果子问题不是独立的,即子问题共享子问题,则分而治之算法反复解决常见的子问题.因此,它做了比必要更多的工作

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

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

换句话说,总共有9个函数调用,但这里只有五个唯一调用(Fibonacci为0到4,包括0和4).如果递归调用在子问题之间共享而不是每次从头开始重新计算,则可以使该算法更有效.这是动态编程背后的关键思想之一.

为了计算F _n(第n个Fibonacci数),上面的代码将总共进行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)中计算斐波纳契数,这比以前快得多.使用一些更高级的数学,我们可以做得更好,但这确实说明了为什么动态编程可以带来不可行的问题并使它们突然变得可行.

希望这可以帮助!