動態規劃

動態規劃（英語：Dynamic programming，簡稱DP）是一種在數學、管理科學、電腦科學、經濟學和生物資訊科學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

動態規劃常常適用於有重疊子問題^[1]和最佳子結構（英語：Optimal substructure）性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化儲存，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。

概述

動態規劃在尋找有很多重疊子問題的情況的最佳解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算並被儲存，從簡單的問題直到整個問題都被解決。因此，動態規劃儲存遞歸時的結果，因而不會在解決同樣的問題時花費不必要的時間。

動態規劃只能應用於有最佳子結構的問題。最佳子結構的意思是局部最佳解能決定全域最佳解（對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。

解決動態規劃問題時，我們需要按照以下步驟系統地思考和解決：

1. 定義狀態：首先要思考如何用數學語言描述問題。定義狀態是整個解題過程中最關鍵的一步，它決定了我們如何儲存和使用計算結果。我們需要仔細思考：要解決的問題需要哪些變數來表示？這些狀態通常會以陣列的形式儲存下來。一個好的狀態定義應該能夠完整地描述問題在某個階段的情況。

2. 找出狀態轉移方程：當我們定義好狀態後，需要思考狀態之間是如何轉移的。也就是說，如何從已知的狀態推導出新的狀態，狀態轉移方程是解決問題的核心，一般想明白狀態轉移方程問題就解決了。

3. 確定初始狀態和邊界條件：有了狀態轉移方程後，我們需要確定問題的初始狀態。同時，我們還需要考慮一些特殊情況，比如輸入為0或負數時應該如何處理。

4. 按照狀態轉移方程求解：最後一步是實際求解過程。我們通常會按照一定的順序（比如從小到大）來計算每個狀態的值。在這個過程中，我們使用已經計算出的狀態值，通過狀態轉移方程來得到新的狀態值。這個過程需要特別注意計算的順序，確保在計算某個狀態時，它依賴的所有狀態都已經計算出來了。^[2]

適用情況

1. 最佳子結構性質。如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。最佳子結構性質為動態規劃演算法解決問題提供了重要線索。
2. 無後效性。即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。
3. 子問題重疊性質。子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地檢視一下結果，從而獲得較高的效率，降低了時間複雜度。

實例

包括但不限於切割鋼條問題、Floyd最短路問題、最大不下降子序列、矩陣鏈乘、凸多邊形三角剖分、背包問題、最長公共子序列、最佳二分搜尋樹等。

硬幣找零問題

硬幣找零問題來自生活中的一個常見場景。給定一組不同面值的硬幣，然後給定一個目標金額。我們的目標是計算出湊到目標金額所需的最少硬幣數量。

我們可以定義狀態 dp[i] 表示：湊出金額 i 所需的最少硬幣數量。假設我們要計算dp[i]，也就是湊出金額 i 所需的最少硬幣數，那麼可以拆分為下面的子問題：

1. 如果我們選擇使用了某個面值 m 的硬幣，那麼問題就轉化為：湊出金額 (i-m) 所需的最少硬幣數，再加上這一個新使用的硬幣；

2. 由於我們要求的是最少硬幣數，所以需要在所有可能的硬幣選擇中取最小值；

因此，狀態轉移方程如下，其中 m 遍歷所有可用的硬幣面值：dp[i] = min(dp[i-m] + 1).

可以在動態規劃之硬幣找零視覺化頁面直觀看到這裏的求解過程。

背包問題

背包問題作為NP完全問題，暫時不存在多項式時間演算法。動態規劃屬於背包問題求解最佳解的可行方法之一。此外，求解背包問題最佳解還有搜尋法等，近似解還有貪婪法等，分數背包問題有最佳貪婪解等。 背包問題具有最佳子結構和重疊子問題。動態規劃一般用於求解背包問題中的整數背包問題（即每種物品所選的個數必須是整數）。 解整數背包問題： 設有${\displaystyle n}$件物品，每件價值記為${\displaystyle P_{i}}$，每件重量記為${\displaystyle W_{i}}$，用一個最大重量為${\displaystyle W}$的背包，求裝入物品的最大價值。 在總重量不超過W的前提下，我們希望總價格最高。對於${\displaystyle Y\leqslant W}$，我們將在總重量不超過${\displaystyle Y}$的前提下，總價格所能達到的最高值定義為${\displaystyle A(Y)}$。${\displaystyle A(W)}$即為問題的答案。

顯然，A(Y)滿足：

• ${\displaystyle A(0)=0}$
• ${\displaystyle A(Y)=\max\{A(Y-1),p_{j}+A(Y-w_{j})\}}$

其中，${\displaystyle p_{j}}$為第${\displaystyle j}$種物品的價格。

對於特例01背包問題（即每件物品最多放1件，否則不放入）的問題，我們將在總重量不超過Y的前提下，前j種物品的總價格所能達到的最高值定義為A(j, Y)。

A(j, Y)的遞推關係為：

• A(0, Y) = 0
• 如果w_j > Y, A(j, Y) = A(j - 1, Y)
• 如果w_j ≤ Y, A(j, Y) = max { A(j - 1, Y), p_j + A(j - 1, Y - w_j)}

參考Pascal代碼

for i:=1 to n do
  for v:=totv downto v[i] do
    f[v]:=max(f[v],f[v-v[i]]+p[i]);
writeln(f[totv]);

參考C++代碼（不含include和陣列聲明）

#define max(x,y) (x)>(y)?(x):(y) //max宏函数，也可以自己寫或者使用algorithm
for(int i=1;i<=n;i++)
  for (v=totv;v>=v[i];v--)
    f[v]=max(f[v],f[v-v[i]]+p[i]);
printf("%d",f[totv]); //或std::cout<<f[totv];

歷史

術語「動態規劃」最初是在1940年代由理查德·貝爾曼用來描述解決問題的過程，在這個過程中，人們需要一個接一個地找到最佳決策。到1953年，他將其精煉成為現代的含義，特別是指將較小的決策問題巢狀在較大的決策中，^[3] 並且該領域隨後被電氣電子工程師學會認可為系統分析和工程學主題。貝爾曼的貢獻以貝爾曼方程的名義被銘記，它是動態規劃的核心結果，它以遞歸形式重申了最佳化問題。

貝爾曼選擇了「動態」這個詞來捕捉問題的隨時間變化的方面，也因為它聽起來令人印象深刻。^[4] 「規劃」一詞指的是使用該方法來找到最佳的「程式」，在於軍事訓練或後勤計劃的意義。這種用法與短語「線性規劃」和「數學規劃」中的用法相同。^[5]

術語起源的上述解釋是不足的。正如羅素和諾維格在他們的書中提到上述故事時所寫的那樣：「這不可能完全正確，因為他的第一篇使用這個詞（貝爾曼，1952）的論文出現在威爾遜於 1953 年成為國防部長之前。」^[6]此外，還有Harold J. Kushner （頁面存檔備份，存於互聯網檔案館）在演講中的評論，他記得貝爾曼。他在談到貝爾曼時參照庫什納的話：「另一方面，當我問他同樣的問題時，他回答說他試圖通過加上動態來超越喬治·伯納德·丹齊格的線性規劃。也許這兩種動機都是正確的。」

使用動態規劃的演算法

• 最長公共子序列
• Floyd-Warshall演算法
• Viterbi演算法
• Kadane's_algorithm^[7]
• 求解馬可夫決策過程下最佳策略^[8]
• 萊文斯坦距離

參考

1. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 'Algorithms', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html （頁面存檔備份，存於互聯網檔案館）
2. 動態規劃硬幣找零問題視覺化
3. Stuart Dreyfus. "Richard Bellman on the birth of Dynamical Programming".
4. Eddy, S. R. What is Dynamic Programming?. Nature Biotechnology. 2004, 22 (7): 909–910. PMID 15229554. S2CID 5352062. doi:10.1038/nbt0704-909.
5. Nocedal, J.; Wright, S. J. Numerical Optimization. Springer. 2006: 9. ISBN 9780387303031.
6. Russell, S.; Norvig, P. Artificial Intelligence: A Modern Approach 3rd. Prentice Hall. 2009. ISBN 978-0-13-207148-2.
7. Maximum_subarray_problem. [2023-01-18]. （原始內容存檔於2023-02-04）.
8. Richard S. Sutton; Andrew G. Barto. Reinforcement Learning: An Introduction Second Edition. The MIT Press. 2018: 73 [2020-08-22]. （原始內容存檔於2022-01-18）. 引文格式1維護：冗餘文字 (link)

外部連結