動態規划算法秘籍

2021-02-15 數據結構與算法

作者丨rainchxy
https://www.jianshu.com/p/0e2d0494593a

本文來自通俗易懂算法入門書《趣學算法》。

動態規劃是1957年理察·貝爾曼在《Dynamic Programming》一書中提出來的，八卦一下，這個人可能有同學不知道，但他的一個算法你可能聽說過，他和萊斯特·福特一起提出了求解最短路徑的Bellman-Ford 算法，該算法解決了Dijkstra算法不能處理負權值邊的問題。

Dynamic Programming，這裡的Programming不是編程的意思，而是指一種表格處理法。我們把每一步得到的子問題結果存儲在表格裡，每次遇到該子問題時不需要再求解一遍，只需要查詢表格即可。

4.1.1 算法思想

動態規劃也是一種分治思想，但與分治算法不同的是，分治算法是把原問題分解為若干子問題，自頂向下，求解各子問題，合併子問題的解從而得到原問題的解。動態規劃也是把原問題分解為若干子問題，然後自底向上，先求解最小的子問題，把結果存儲在表格中，在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重複計算，從而提高算法效率。

4.1.2 算法要素

什麼問題可以使用動態規劃呢？我們首先要分析問題是否具有以下兩個性質：

（1）最優子結構

最優子結構性質是指問題的最優解包含其子問題的最優解。最優子結構是使用動態規劃的最基本條件，如果不具有最優子結構性質就不可以使用動態規劃解決。


（2）子問題重疊

子問題重疊是指在求解子問題的過程中，有大量的子問題是重複的，那麼只需要求解一次，然後把結果存儲在表中，以後使用時可以直接查詢，不需要再次求解。子問題重疊不是使用動態規劃的必要條件，但問題存在子問題重疊更能夠充分彰顯動態規劃的優勢。

什麼問題可以使用動態規劃呢？我們首先要分析問題是否具有以下兩個性質：

（1）最優子結構

最優子結構性質是指問題的最優解包含其子問題的最優解。最優子結構是使用動態規劃的最基本條件，如果不具有最優子結構性質就不可以使用動態規劃解決。

（2）子問題重疊

子問題重疊是指在求解子問題的過程中，有大量的子問題是重複的，那麼只需要求解一次，然後把結果存儲在表中，以後使用時可以直接查詢，不需要再次求解。子問題重疊不是使用動態規劃的必要條件，但問題存在子問題重疊更能夠充分彰顯動態規劃的優勢。

4.1.1 解題秘籍

遇到一個實際問題，如何採用動態規劃來解決呢？

（1） 分析最優解的結構特徵。

（2） 建立最優值的遞歸式。

（3） 自底向上計算最優值，並記錄。

（4） 構造最優解。

本章通過8個實例，講解了動態規劃的解題過程。動態規劃求解最優化問題時需要考慮兩個性質：最優子結構和子問題重疊，只要滿足最優子結構性質就可以使用動態規劃，如果還具有子問題重疊，則更能彰顯動態規劃的優勢。判斷可以使用動態規劃後，就可以分析其最優子結構特徵，找到原問題和子問題的關係，從而得到最優解遞歸式。然後按照最優解遞歸式自底向上求解，採用備忘機制(查表法)有效解決子問題重疊，重複的子問題不需要重複求解，只需查表即可。

動態規劃的關鍵：

(1)最優子結構判定

a. 作出一個選擇；

b. 假定已經知道了哪種選擇是最優的；

例如矩陣連乘問題，我們假設已經知道在第k個矩陣加括號是最優的，即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。

c. 最優選擇後會產生哪些子問題；

例如矩陣連乘問題，我們作出最優選擇後產生兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)。

d. 證明原問題的最優解包含其子問題的最優解。

通常使用「剪切—粘貼」反證法。證明如果原問題的解是最優解，那么子問題的解也是最優解。反證：假定子問題的解不是最優解，那麼就可以將它「剪切」掉，把最優解「粘貼」進去，從而得到一個比原問題最優解更優的解，這與前提原問題的解是最優解矛盾。得證。

例如：矩陣連乘問題，c=a+b+d，我們只需要證明如果c是最優的，則a和b一定是最優的（即原問題的最優解包含子問題的最優解）。

反證法：如果a不是最優的，(AiAi+1…Ak) 存在一個最優解aˊ，aˊ

(2)如何得到最優解遞歸式

a.分析原問題最優解和子問題最優解的關係；

例如矩陣連乘問題，我們假設已經知道在第k個矩陣加括號是最優的，即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。作出最優選擇後產生兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)。如果我們用m[i][j]表示AiAi+1…Aj矩陣連乘的最優解，那麼兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)對應的最優解分別是m[i][k]，m[k+1][j]。剩下的只需要考察(AiAi+1…Ak)和(Ak+1Ak+2…Aj)的結果矩陣相乘的乘法次數了。兩個結果矩陣相乘的乘法次數是pi*pk+1*qj。

因此，原問題最優解和子問題最優解的關係：m[i][j]= m[i][k]+m[k+1][j]+ pi*pk+1*qj

b.考察有多少種選擇；

實質上，我們並不知道哪種選擇是最優的，因此就需要考察有多少種選擇，然後從這些選擇中找到最優解。

例如矩陣連乘問題，加括號的位置k(AiAi+1…Ak)(Ak+1Ak+2…Aj)，k的取值範圍是{i，i+1，…，j-1}，即i≤k

c.得到最優解遞歸式。

例如矩陣連乘問題，m[i][j]表示AiAi+1…Aj矩陣連乘的最優解，根據最優解和子問題最優解的關係，並考察所有的選擇，找到最小值就是我們要的最優解。

 推薦↓↓↓ 

涵蓋：程式設計師大咖、源碼共讀、程式設計師共讀、數據結構與算法、黑客技術和網絡安全、大數據科技、編程前端、Java、Python、Web編程開發、Android、iOS開發、Linux、資料庫研發、幽默程式設計師等。

相關焦點

  • 五大常用算法:動態規划算法
    （該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規划算法同其他算法相比就不具備優勢）四、求解的基本步驟動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。
  • 【算法學習】動態規劃
    今天咱們來聊聊動態規劃。動態規劃(dynamic programming)是一種基礎的算法設計思想。作為一種尋找最優解的通用方法，它是在20世紀50年代由美國數學家Richard Bellman（也就是之前最短路徑問題中Bellman ford算法的發明者之一）所發明的。
  • 經典算法研究系列 之 動態規划算法
    數經典算法研究系列 之基本概念動態規划過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規划算法同其他算法相比就不具備優勢）求解的基本步驟動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。
  • 如何掌握動態規划算法的套路?
    動態規劃(Dynamic Programming)，簡稱DP，這個名字給人的感覺是一種非常高大上非常複雜的算法，很多同學看到這個名字可能就會望而卻步，在面試的時候也非常害怕被問到動態規劃的題目。實際上，它並不是不是一種確定的算法，它是一種最優化的方法求解問題的思想或方法。它是由美國數學家貝爾曼(Bellman)在研究多階段決策過程的優化問題時提出。不過，與之對應的還有一些與時間無關的靜態規劃，如：線性規劃、非線性規劃等。在運籌學中，動態規劃是的非常重要的內容，在各個行業領域都有著廣泛的應用。我們如何理解動態規劃?
  • 一文讀懂動態規划算法
    （該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規划算法同其他算法相比就不具備優勢）求解的基本步驟動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。
  • 動態規划算法Dynamic Programming
    動態規劃與分治法相似，都是通過組合子問題的解來求解原問題。不同的是，分治法將問題劃分為互不相交的子問題，遞歸的求解子問題，再將他們的解組合起來，求出原問題的解。與之相反，動態規劃應用於子問題重疊的情況，即不同的子問題具有公共的子子問題。在這種情況下，分治法會做許多不必要的工作，他會反覆求解那些公共子子問題。
  • 動態規劃之 KMP 算法詳解
    為什麼我認為 KMP 算法就是個動態規劃問題呢，等會有解釋。對於動態規劃，之前多次強調了要明確dp數組的含義，而且同一個問題可能有不止一種定義dp數組含義的方法，不同的定義會有不同的解法。讀者見過的 KMP 算法應該是，一波詭異的操作處理pat後形成一個一維的數組next，然後根據這個數組經過又一波複雜操作去匹配txt。時間複雜度 O(N)，空間複雜度 O(M)。
  • 拒絕遺忘:高效的動態規划算法
    不懂動態規劃的人會在解決過的問題上再次浪費時間，懂的人則會事半功倍。那麼什麼是動態規劃？這種算法有何神奇之處？本文作者給出了初步的解答。假設你正在使用適當的輸入數據進行一些計算。你在每個實例中都進行了一些計算，以便得到一些結果。當你提供相同的輸入時，你不知道會有相同的輸出。這就像你在重新計算之前已經計算好的特定結果一樣。那麼問題出在哪裡呢？
  • 動態規划算法入門,這就夠了
    動態規劃（Dynamic programming，簡稱DP），是大家都覺得比較難以掌握的算法。為了應付面試，我們經常會背誦一下斐波那楔數列或者背包問題的源碼，其實，只要理解了思想，掌握基本的模型，然後再來點寫代碼的套路，動態規劃並沒有那麼難。
  • 如何掌握動態規划算法的套路? - 51CTO.COM
    動態規劃(Dynamic Programming)，簡稱DP，這個名字給人的感覺是一種非常高大上非常複雜的算法，很多同學看到這個名字可能就會望而卻步，在面試的時候也非常害怕被問到動態規劃的題目。實際上，它並不是不是一種確定的算法，它是一種最優化的方法求解問題的思想或方法。它是由美國數學家貝爾曼(Bellman)在研究多階段決策過程的優化問題時提出。不過，與之對應的還有一些與時間無關的靜態規劃，如：線性規劃、非線性規劃等。在運籌學中，動態規劃是的非常重要的內容，在各個行業領域都有著廣泛的應用。我們如何理解動態規劃?
  • 動態規划算法,3000字真正幫助你入門
    本文目標幫助朋友們認識到動態規划算法之美，從而引發學習它、研究它的興趣。一 動態規劃引言某個問題一旦找到動態規劃的解法，一般便是接近或就是最優解法，也正因為此，無數程式設計師為它著迷，大廠面試也是必考。但是，動態規劃又非常靈活，本質上沒有套路，問題不同，動態規劃的迭代方程就不同。
  • Java動態規划算法策略
    Dynamic Programming是五大常用算法策略之一，簡稱DP，譯作中文是「動態規劃」，可就是這個聽起來高大上的翻譯坑苦了無數人，因為看完這個算法你可能會覺得和動態規劃根本沒太大關係，它對「動態」和「規劃」都沒有太深的體現。
  • 豁然開朗經典算法之「動態規劃」
    《算法導論》是這樣解釋動態規劃的：動態規劃與分治法相似，都是通過組合子問題的解來求解原問題答案，將問題劃分為互不相交的子問題，遞歸的求解子問題，最後合併子問題的答案，得到原問題的答案。翻譯成人話就是：計算並存儲小問題的解，並將這些解組合成大問題的解。
  • 算法篇:動態規劃(二)
    算法：本篇屬於動態規劃的進階題目，我們可以通過數據dp[i]來表示包括第i個元素的計算和
  • 我的第437篇原創:動態規划算法入門篇,真正幫助你入門!!!
    本文目標幫助朋友們認識到動態規划算法之美，從而引發學習它、研究它的興趣。一 動態規劃引言某個問題一旦找到動態規劃的解法，一般便是接近或就是最優解法，也正因為此，無數程式設計師為它著迷，大廠面試也是必考。但是，動態規劃又非常靈活，本質上沒有套路，問題不同，動態規劃的迭代方程就不同。
  • 深入理解動態規划算法 | 最長公共子序列LCS
    通過歡迎點擊「算法與編程之美」↑關注我們！
  • 總結 | 動態規劃十問十答
    動態規劃是IT技術面試中最難的算法，很多人披荊斬棘，最終還是跪在動態規劃題目上。
  • 乾貨總結 | 動態規劃十問十答
    動態規劃是IT技術面試中最難的算法，很多人披荊斬棘，最終還是跪在動態規劃題目上。
  • 數模天空|動態規劃
    動態規劃（dynamic programming）是運籌學的一個分支，是求解決策過程（decision  process）最優化的數學方法。動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。
  • 動態規劃思想及經典算法
    通常情況下，子問題具有一定的相似性，因此，動態規劃試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定的子問題的解已經算出，則將其存儲，以便下次需要同一個子問題時直接查表使用。分治與動態規劃共同點：二者都要求原問題具有最優子結構，都是將原問題進行分解，分而治之，分解成若干個子問題，然後將子問題的解進行合併，形成原問題的解。