動態規劃簡介

Created: November-22, 2018

動態程式設計通過將解決方案與子問題相結合來解決問題。它可以類似於分而治之的方法，其中問題被劃分為不相交的子問題，子問題被遞迴地求解，然後組合以找到原始問題的解。相反，動態程式設計在子問題重疊時適用 - 也就是說，當子問題共享子問題時。在這種情況下，分而治之的演算法比必要的工作更多，重複解決常見的子問題。動態程式設計演算法只解決每個子子問題一次，然後將其答案儲存在表中，從而避免每次解決每個子子問題時重新計算答案的工作。

我們來看一個例子。我們通常稱為 Fibonacci 的義大利數學家 Leonardo Pisano Bigollo 通過考慮兔子種群的理想化增長發現了一系列。該系列是：

1, 1, 2, 3, 5, 8, 13, 21, ......

我們可以注意到前兩個後面的每個數字都是前面兩個數字的總和。現在，讓我們制定一個函式 F(n) ，它將返回第 n 個 Fibonacci 數，這意味著，

F(n) = nth Fibonacci Number

到目前為止，我們已經知道，

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

我們可以通過以下方式概括：

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

現在，如果我們想將它寫為遞迴函式，我們將 F(1) 和 F(2) 作為基本情況。所以我們的 Fibonacci 函式將是：

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

現在，如果我們呼叫 F(6)，它將呼叫 F(5) 和 F(4)，這將呼叫更多。讓我們以圖形方式表示：

https://i.stack.imgur.com/ngSbS.jpg

從圖中可以看出，F(6) 將呼叫 F(5) 和 F(4)。現在 F(5) 將呼叫 F(4) 和 F(3)。在計算 F(5) 之後，我們可以肯定地說已經計算了 F(5) 呼叫的所有函式。這意味著，我們已經計算了 F(4)。但我們再次計算 F(4)，因為 F(6) 的右孩子指示。我們真的需要重新計算嗎？我們可以做的是，一旦我們計算了 F(4) 的值，我們就將它儲存在一個名為 dp 的陣列中，並在需要時重用它。我們將使用 -1 （或我們計算中不會出現的任何值）初始化我們的 dp 陣列。然後我們將呼叫 F(6) ，其中我們修改的 F(n) 將如下所示： **** **** ****

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

我們完成了與以前相同的任務，但只進行了簡單的優化。也就是說，我們使用了 memoization 技術。首先， dp 陣列的所有值都是 -1 。當呼叫 F(4) 時，我們檢查它是否為空。如果它儲存 -1 ，我們將計算其值並將其儲存在 dp [4]中。如果它儲存除 -1 以外的任何東西，那意味著我們已經計算了它的值。所以我們只需返回值。

使用 memoization 的這種簡單優化稱為動態程式設計。

如果動態程式設計具有某些特徵，則可以解決該問題。這些是：

子問題：
DP 問題可以分為一個或多個子問題。例如：F(4) 可以分為更小的子問題 F(3) 和 F(2)。由於子問題類似於我們的主要問題，這些可以使用相同的技術來解決。
重疊子問題：
DP 問題必須具有重疊的子問題。這意味著必須有一些共同的部分，不止一次呼叫相同的函式。例如：F(5) 和 F(6) 共有 F(3) 和 F(4)。這就是我們將值儲存在陣列中的原因。

https://i.stack.imgur.com/7OVJm.jpg

最佳子結構：
假設你被要求最小化功能 g(x)。你知道 g(x) 的價值取決於 g(y) 和 g(z)。現在，如果我們可以通過最小化 g(y) 和 g(z) 來最小化 g(x)，那麼我們就可以說問題具有最優的子結構。如果通過僅最小化 g(y) 來最小化 g(x) 並且如果最小化或最大化 g(z) 對 g(x) 沒有任何影響，則該問題不具有最佳子結構。簡單來說，如果問題的最優解可以從其子問題的最優解中找到，那麼我們可以說問題具有最優的子結構性質。