動態規劃和分而治之

Question

我在讀notes on Dynamic programming，我遇到了以下評論。

如果子問題不是獨立的，即 子問題份額subsubproblems，然後分而治之算法反覆解決常見 subsubproblems。 因此，它做了比必要的更多的工作

這是什麼意思？你能否舉例說明上述觀點？

Answer 1

作者提到這樣一個事實，即許多分治算法具有相互重疊的子問題。舉個例子，這個非常簡單的斐波那契實現：

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

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

如果你描繪出做計算斐波那契調用（4），我們得到

• 斐波那契（4）調用斐波那契（3）斐波那契（2）
• 斐波那契（3）調用斐波那契（2）和斐波納契（1）
• 斐波那契（2）調用斐波那契（1）和Fibonacci（0）
• 斐波那契（2）（另一種）調用Fibonacci（1）和Fibonacci（0）
• 斐波那契（1）終止。
• 斐波那契（1）終止。
• 斐波那契（1）終止。
• 斐波那契（0）終止。
• 斐波那契（0）終止。

換句話說，總共有9個函數調用，但這裏只有5個唯一的調用（0到4的斐波那契數）。如果遞歸調用在子問題之間共享，而不是每次重新從頭開始重新計算，則可以使此算法效率更高。這是動態編程背後的關鍵思想之一。

爲了計算˚F_Ñ（第n Fibonacci數），上面的代碼將使共2F _{n + 1個} - 1遞歸調用。由於斐波納契數字以指數級快速增長，這需要指數級的許多工作。但是，有可能使用這樣的事實，即許多遞歸調用是相同的，從而大大簡化了這一點。而不是從斐波那契（4）開始並繼續下去，讓我們從斐波那契（0）開始並着手。具體而言，我們將構建的表（讓我們稱之爲FTable）長度爲5，並且將在如下填充：

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

現在，假設我們要計算FTable [2]。這要求我們知道FTable [0]和FTable [1]，但我們已經知道，因爲他們在桌子上。因此，我們可以設置

• FTable [2] = 1

使用類似的邏輯，我們可以計算FTable [3]從FTable [2]和FTable [1]：

• FTable [3] = 2

而且FTable [4]從FTable [2]和FTable [3]：

• FTable [4] = 3

注意我們如何迴避賺很多的只是建立起來以相反的順序重疊的遞歸調用！這現在計算時間O（n）上的斐波那契數，它比以前快得多。使用一些更高級的數學，我們甚至可以做得比這更好，但是這確實說明了爲什麼動態編程會帶來不可行的問題，並使它們突然變得可行。

希望這會有所幫助！