動態規劃

動態規劃方法類似於分治法，將問題分解成越來越小的子問題。但與分治法不同的是，這些子問題不是獨立解決的。相反，這些較小子問題的結果會被記住並用於類似的或重疊的子問題。

大多數情況下，動態規劃演算法用於解決最佳化問題。在解決手頭的子問題之前，動態演算法會嘗試檢查先前解決的子問題的結果。子問題的解被組合起來以獲得最佳最終解。因此，這種範例被稱為自底向上方法。

所以我們可以得出結論：

• 問題應該能夠被分解成更小的重疊子問題。

• 可以使用較小子問題的最優解來獲得最終的最優解。

• 動態演算法使用記憶化。

然而，在一個問題中，兩個主要屬性可以表明給定的問題可以使用動態規劃來解決。它們是：

重疊子問題

與分治法類似，動態規劃也組合子問題的解。它主要用於一個子問題的解需要重複使用的地方。計算出的解儲存在一個表中，因此不必重新計算。因此，當存在重疊子問題時，需要這種技術。

例如，二分查詢沒有重疊子問題。而斐波那契數的遞迴程式有很多重疊子問題。

最優子結構

如果給定問題的最優解可以使用其子問題的最優解獲得，則給定問題具有最優子結構屬性。

例如，最短路徑問題具有以下最優子結構屬性：

如果節點x位於從源節點u到目標節點v的最短路徑中，則從u到v的最短路徑是從u到x的最短路徑和從x到v的最短路徑的組合。

像Floyd-Warshall和Bellman-Ford這樣的標準全對最短路徑演算法是動態規劃的典型例子。

動態規劃方法的步驟

動態規劃演算法的設計遵循以下四個步驟：

• 描述最優解的結構。

• 遞迴地定義最優解的值。

• 計算最優解的值，通常以自底向上的方式。

• 根據計算出的資訊構造最優解。

動態規劃與貪心演算法與分治法的比較

與解決區域性最佳化的貪心演算法相比，動態演算法的目標是對問題進行全域性最佳化。

與分治演算法（其中解被組合以獲得全域性解）相比，動態演算法使用較小子問題的輸出，然後嘗試最佳化較大的子問題。動態演算法使用記憶化來記住已解決子問題的輸出。

動態規劃的例子

以下計算機問題可以使用動態規劃方法解決：

• 矩陣鏈乘法

• Floyd-Warshall演算法

• 0-1揹包問題

• 最長公共子序列演算法

• 旅行商問題（動態規劃）

動態規劃可以自頂向下和自底向上兩種方式使用。當然，大多數情況下，參考之前的解輸出比重新計算在CPU週期方面更便宜。