動態規劃：它是什麼、它是如何工作的以及學習資源

動態規劃是由數學家和經濟學家理查德貝爾曼提出的概念。

當時，貝爾曼正在尋找解決複雜優化問題的方法。 優化問題要求您從一組選項中選擇最佳解決方案。

優化問題的一個例子是旅行商問題。 目標是找到最短路線，讓推銷員恰好訪問每個城市一次並返回出發城市。

貝爾曼解決這些問題的方法是將它們分解成更小的子問題，並從小到大解決子問題。 然後他存儲子問題的結果，並重新使用它們來解決更大的子問題。 這是動態規劃背後的主要思想。

什麼是動態規劃？

動態規劃通過將優化問題分解為更小的子問題來解決優化問題，對每個子問題求解一次，並存儲它們的解，以便它們可以被重用和組合以解決更大的問題。 問題從小到大解決，允許重複使用解決方案。

動態規劃是如何工作的？

使用動態規劃解決問題涉及以下步驟：

1. 定義子問題：一個大問題被分成小的子問題。
2. 解決子問題：這涉及解決已識別的子問題，這可以使用遞歸或迭代來完成。
3. 存儲解決方案：存儲子問題的解決方案，以便可以重複使用。
4. 構建原始問題的解決方案：大問題的解決方案是從已經計算好的子問題中構建的。

為了解實際效果，我們使用此過程計算第 6 個斐波那契數 F(6)。

首先，定義需要解決的子問題。

F(n) = F(n-1) + F(n-2) 對於 n > 1

因此：F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

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

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

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

第二步涉及使用遞歸函數或迭代過程解決每個子問題。 我們從最小到最大解決子問題，重用較小子問題的結果。 這給了我們以下信息：

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

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

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

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

F(6) = F(5) + F(4) = 5 + 3 = 8

當我們解決每個子問題時，我們將解決方案存儲在數組或表中，以便它們可以在解決更大的子問題時重複使用，如下所示：

一旦解決了所有子問題，我們就使用這些解決方案來構建原始問題的解決方案。

在這種情況下，原始問題的解決方案是第 6 個斐波那契數，它是通過對 F(5) 和 F(4) 的結果求和而找到的，這些子問題是從最大問題中識別出來的。 結果給了我們 8。

在哪里以及為什麼使用動態規劃？

動態規劃用於我們遇到的問題可以分解為更小的子問題的領域，它們的解決方案用於解決更大的問題。

這些領域包括計算機科學、經濟學、數學和工程學。 在計算機科學中，它用於解決涉及序列、圖形和整數值的問題以及競爭性編程。

在經濟學中，它用於解決金融、生產和資源配置中的優化問題。 在數學中，動態規劃用於博弈論、統計學和概率論，用於解決優化問題。

在工程中，它用於解決資源分配、調度、製造、通信和控制系統中的問題。

使用動態規劃解決優化問題有幾個優點：

1. 效率：動態規劃比其他優化算法更高效，因為它避免了多次重新計算類似問題。
2. 解決大問題：動態規劃非常適合解決使用其他方法無法解決的大型優化問題。 這是因為它將問題分解為更小的問題，降低了它們的複雜性。
3. 最優解：如果子問題和目標定義正確，動態規划算法可以找到問題的最優解。
4. 簡單性：動態規划算法易於實現和理解，尤其是當問題可以按特定順序定義時。
5. 可擴展性：通過添加額外的子問題和修改問題的目標，可以輕鬆擴展動態規划算法以解決更複雜的問題。

在解決優化問題時，動態規劃是確保解決方案效率的非常有用的工具。

動態規劃中使用的方法

在動態規劃中，有兩種​​方法用於解決優化問題。 這些是自上而下的方法和自下而上的方法。

自上而下的方法

這種方法也稱為記憶化。 記憶化是一種優化技術，主要用於通過將函數調用的結果存儲在緩存中並在下次需要時返回緩存的結果而不是再次計算它們來使計算機程序更快。

自上而下的方法涉及遞歸和緩存。 遞歸涉及一個函數以問題的更簡單版本作為參數調用自身。 遞歸用於將問題分解為更小的子問題並解決子問題。

一旦解決了一個子問題，它的結果就會被緩存起來，並在類似問題出現時重新使用。 自上而下易於理解和實施，並且只解決一個子問題一次。 然而，它的一個缺點是它會因為遞歸而佔用大量內存。 這可能導致堆棧溢出錯誤。

自下而上的方法

自下而上的方法，也稱為製表法，取消了遞歸，代之以迭代，從而避免了堆棧溢出錯誤。

在這種方法中，一個大問題被分解成更小的子問題，然後使用子問題的解決方案來解決更大的問題。

較小的子問題首先從大到小求解，其結果存儲在矩陣、數組或表中，因此得名製表。

存儲的結果解決了依賴於子問題的更大問題。 然後通過使用先前計算的值解決最大的子問題來找到原始問題的結果。

這種方法的優點是通過消除遞歸來提高內存和時間效率。

動態規劃可以解決的問題的例子

以下是一些可以使用動態規劃解決的編程問題：

#1。 背包問題

背包是由帆布、尼龍或皮革製成的包，通常背在背上，供士兵和徒步旅行者用來攜帶補給品。

在背包問題中，系統會向您展示一個背包，鑑於它的承載能力，您需要選擇物品，每件物品都有其價值。 您的選擇應該使您獲得最大的物品總價值，並且物品的重量小於或等於背包容量。

背包問題的一個例子如下：

想像一下，您正在徒步旅行，並且有一個容量為 15 公斤的背包。 您有一份可以隨身攜帶的物品清單，以及它們的價值和重量，如下表所示：

選擇要攜帶的物品的子集，使物品的總價值最大化，同時總重量小於或等於背包容量，即 15 公斤。

背包問題的實際應用涉及選擇證券以添加到投資組合中以最小化風險和最大化利潤，以及找到減少原材料浪費最少的方法。

#2。 調度問題

調度問題是一個優化問題，其目標是將任務最優地分配給一組資源。 資源可以是用於完成任務的機器、人員或其他資源。

下面給出了一個調度問題的例子：

假設您是一名項目經理，負責安排一組需要由一組員工完成的任務。 每個任務都有一個開始時間、一個結束時間，以及一個有資格完成它的員工列表。

下表描述了任務及其特徵：

將每項任務分配給一名員工，以最大限度地減少總完成時間。

在試圖優化機器、材料、工具和勞動力等資源的分配時，製造業可能會遇到調度問題。

在優化床位、人員和醫療用品的使用時，它也可能在醫療保健中遇到。 其他可能出現此問題的行業是項目管理、供應鏈管理和教育。

#3。 旅行商問題

這是研究最多的優化問題之一，可以使用動態規劃來解決。

旅行商問題提供了一個城市列表和每對城市之間的距離。 您需要找到訪問每個城市恰好一次並返回起點城市的最短路線。

下面給出了旅行商問題的示例：

想像一下，您是一名銷售人員，需要在盡可能短的時間內訪問一組城市。 你有一個你需要訪問的城市列表以及每對城市之間的距離，如下表所示：

旅行商問題可能在休閒行業試圖為遊客規劃路線時遇到，物流在規劃貨物運輸時遇到，交通運輸在規劃公交線路時遇到，在銷售行業等等。

顯然，動態規劃在現實世界中有很多應用，這有助於進一步了解它。

考慮以下資源來闡述您的動態規劃知識。

資源

Richard Bellman 的動態規劃

Dynamic Programming 是 Richard Bellman 的一本書，他提出了動態規劃並在其早期階段進行了開發。

預習	產品	評分	價格
	動態規劃（多佛計算機科學書籍）	暫無評分	17.29 美元	在亞馬遜上購買

本書以通俗易懂的方式編寫，只需要數學和微積分的基本知識即可理解文本。 在書中，貝爾曼介紹了多階段決策過程的數學理論，這是動態規劃的關鍵。

然後，本書研究了多階段生產過程中的瓶頸問題、存在唯一性定理以及最優庫存方程。

這本書最棒的地方在於，貝爾曼提供了物流、調度理論、通信理論、數理經濟學和控製過程等領域的許多複雜問題的例子，並展示了動態規劃如何解決這些問題。

這本書有 Kindle、精裝和平裝版。

動態規划算法碩士課程

Udemy 的動態編程算法碩士課程由 Google 的軟件工程師 Apaar Kamal 和也曾在 Google 工作的 Prateek Narang 提供。

該課程經過優化，可幫助學習者在編程競賽中脫穎而出，該競賽具有許多需要動態編程的問題。

除了編程競賽者之外，該課程非常適合希望提高對算法的理解的程序員以及準備編程面試和在線編碼輪次的人員。

該課程時長超過 40 小時，深入介紹了動態規劃。 該課程首先提供遞歸和回溯等概念的複習。

然後涵蓋博弈論中的動態規劃、字符串、樹和圖、矩陣求冪、位掩碼、組合學和子序列、劃分問題和多維動態規劃，以及許多其他概念。

競爭性編程基礎，精通算法

Udemy 提供了由 Prateek Narang 和 Amal Kamaar 編寫的競爭性編程基礎課程，該課程以對競爭性程序員有用且相關的方式涵蓋動態編程、數學、數論以及高級數據結構和算法。

在深入研究在競爭性編程中派上用場的更複雜的算法和技術之前，該課程提供了對數據結構和算法的複習。

該課程涵蓋動態規劃、數學、博弈論、模式匹配、位掩碼以及在編程競賽中使用和測試的無數高級算法。

Udemy 課程分為 10 個模塊和 42 個部分，並在每個部分後提供大量練習題。 對於任何對競爭性編程感興趣的人來說，這本暢銷書課程都是必備的。

最後的話

動態編程對於任何程序員來說都是一項有益的技能，可以通過學習提高他們對現實世界問題的解決能力。 因此，程序員應該考慮通過建議的資源將這個重要工具添加到他們的工具箱中。

接下來，您可以查看用於數據科學的編程語言。