7號晚聽了鄒博一次微課，正好是自己最近正在死磕的動態(tài)規(guī)劃，所以搬好小板凳聽鄒博講解動態(tài)規(guī)劃。現(xiàn)將內(nèi)容整理如下：

內(nèi)容主要分為兩個部分：

1. 動態(tài)規(guī)劃和貪心的認識——工具：馬爾科夫過程

2. 動態(tài)規(guī)劃，通過3個DP中的經(jīng)典問題詳細講解

　　1）最長遞增子序列LIS

　　2）格子取數(shù)/走棋盤問題及應用

　　3）找零錢/背包問題

正題開始。首先，人們認識事物的方法有三種：通過概念（即對事物的基本認識）、通過判斷（即對事物的加深認識）、和推理（對事物的深層認識）。其中，推理又包含歸納法和演繹法。（這些從初中高中一直到大學我們都是一直在學習的，關鍵是理解）

歸納法是從特殊到一般，屬于發(fā)散思維；（如：蘇格拉底會死；張三會死；李四會死；王五會死……，他們都是人。所以，人都會死。）

演繹法是從一般到特殊，屬于匯聚思維。（如：人都會死的；蘇格拉底是人。所以，蘇格拉底會死。）

?

那么，如何用歸納法解決數(shù)學問題，進行應用呢？

已知問題規(guī)模為n的前提A，求解一個未知解B。（我們用An表示“問題規(guī)模為n的已知條件”）

此時，如果把問題規(guī)模降到0，即已知A0，可以得到A0->B.

• 如果從A0添加一個元素，得到A1的變化過程。即A0->A1; 進而有A1->A2; A2->A3; …… ; Ai->Ai+1. 這就是嚴格的歸納推理，也就是我們經(jīng)常使用的數(shù)學歸納法；
• 對于Ai+1，只需要它的上一個狀態(tài)Ai即可完成整個推理過程（而不需要更前序的狀態(tài)）。我們將這一模型稱為馬爾科夫模型。對應的推理過程叫做“貪心法”。

然而，Ai與Ai+1往往不是互為充要條件，隨著i的增加，有價值的前提信息越來越少，我們無法僅僅通過上一個狀態(tài)得到下一個狀態(tài)，因此可以采用如下方案：

• {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 這種方式就是第二數(shù)學歸納法。
• 對于Ai+1需要前面的所有前序狀態(tài)才能完成推理過程。我們將這一模型稱為高階馬爾科夫模型。對應的推理過程叫做“動態(tài)規(guī)劃法”。

上述兩種狀態(tài)轉(zhuǎn)移圖如下圖所示：

? ? ? ? ? ? ?

?

下面通過分析幾個經(jīng)典問題來理解動態(tài)規(guī)劃。

實例一：最長遞增子序列（Longest Increasing Subsequence）。

問題描述。給定長度為N的數(shù)組A，計算A的最長單調(diào)遞增的子序列（不一定連續(xù)）。如給定數(shù)組A{5，6，7，1，2，8}，則A的LIS為{5，6，7，8}，長度為4.

思路：因為子序列要求是遞增的，所以重點是子序列的起始字符和結(jié)尾字符，因此我們可以利用結(jié)尾字符。想到：以A[0]結(jié)尾的最長遞增子序列有多長？以A[1]結(jié)尾的最長遞增子序列有多長？……以A[n-1]結(jié)尾的最長遞增子序列有多長？分析如下圖所示：

? ? ? ? ? ? ??

?

• （動態(tài)規(guī)劃solution）所以我們可以使用一個額外的空間來保存前面已經(jīng)算得的最長遞增子序列，然后每次更新當前的即可。也就是問題演化成：已經(jīng)計算得到了b[0,1,2,……,i-1]，如何計算得到b[i]呢？

顯然，如果ai>=aj，則可以將ai放到b[j]的后面，得到比b[j]更長的子序列。從而：b[i] = max{b[j]}+1. s.t. A[i] > A[j] && 0 <= j < i.

所以計算b[i]的過程是，遍歷b[i]之前的所有位置j，找出滿足關系式的最大的b[j].

得到b[0...n-1]之后，遍歷所有的b[i]找到最大值，即為最大遞增子序列。 總的時間復雜度為O(N2).

我實現(xiàn)的Java版代碼為：

publi int LIS(int[] A) {if(A == null || A.length == 0)return 0;int[] b = new int[A.length];b[0] = 1;int result = 1;for(int i=1; i<A.length; i++) {int max = -1;for(int j=0; j<i; j++) {if(A[j] < A[i] && b[j] > max)max = b[j];}b[i] = max + 1;result = Math.max(result, b[i]);}return result;} View Code

?

進而，如果不僅是求LIS的長度，而要求LIS本身呢？我們可以通過記錄前驅(qū)的方式，從該位置找到其前驅(qū)，進而找到前驅(qū)的前驅(qū)……

Java代碼如下：

public static ArrayList<Integer> LISDetail(int[] A) {if(A == null || A.length == 0)return null;int[] b = new int[A.length];int[] b1 = new int[A.length];b[0] = 1;b1[0] = -1;int result = 1;int index = 0;for(int i=1; i<A.length; i++) {int max = 0;boolean flag = false;for(int j=0; j<i; j++) {if(A[j] < A[i] && b[j] > max) {flag = true;max = b[j];b1[i] = j;}}if(flag == false) b1[i] = -1;b[i] = max + 1;if(result < b[i]) {result = b[i];index = i;}}ArrayList<Integer> res = new ArrayList<Integer>();//res.add(A[index]);for(;index >=0; ) {res.add(A[index]);index = b1[index];}Collections.reverse(res);return res;} View Code

?

使用動態(tài)規(guī)劃方法的到O(N2)的時間復雜度算法，能否有更優(yōu)的方法呢？

• （貪心算法solution）我們?nèi)匀皇褂蒙厦娴睦?#xff0c;用其他的思路試試。我們遞增式的選擇元素，讓每一次的選擇盡可能的小，實際操作如下：

最開始，緩沖區(qū)里為空；

看到了字符“1”，添加到緩沖區(qū)的最后，即緩沖區(qū)中是“1”；

看到了字符“4”，“4”比緩沖區(qū)的所有字符都大，因此將“4”添加到緩沖區(qū)的最后，得到“14”；

看到了字符“6”，“6”比緩沖區(qū)的所有字符都大，因此將“6”添加到緩沖區(qū)的最后，得到“146”；

看到了字符“2”，“2”比“1”大，比“4”小，因此將“4”直接替換成“2”，得到“126”；

看到了字符“8”，“8”比緩沖區(qū)的所有字符都大，因此將“8”添加到緩沖區(qū)的最后，得到“1268”；

看到了字符“9”，“9”比緩沖區(qū)的所有字符都大，因此將“9”添加到緩沖區(qū)的最后，得到“12689”；

看到了字符“7”，“7”比“6”大，比“8”小，因此將“8”直接替換成“7”，得到“12679”；

現(xiàn)在，緩沖區(qū)的字符數(shù)目為5，因此，數(shù)組A的LIS的長度就是5！

這樣，時間復雜度變?yōu)槊看味荚谝粋€遞增的序列中替換或插入一個新的元素，所以為O(nlogn)。

代碼為：

public int len = 0;public int LIS1(int[] A) {if(A == null || A.length == 0)return 0;int[] b = new int[A.length];b[0] = A[0];len = 1;for(int i=1; i<A.length; i++) {insert(b, A[i]);}return len;}public int[] insert(int[] a, int val) {if(val < a[0]) {a[0] = val;return a;}if(val > a[len-1]) {a[len] = val;len++;return a;}int left = 0, right = len-1, mid = (left + right) / 2;while(left < right) {mid = (left + right) / 2;if(a[mid] < val && a[mid+1] >= val) {a[mid+1] = val;return a;}if(a[mid] >= val && a[mid-1] < val) {a[mid] = val;return a;}if(a[mid] < val) left = mid+1;if(a[mid] > val)right = mid-1;}return a;} View Code

?

但后來我分析了這種方法只能得到長度，不能得到子序列本身。（老師上課時提示說考慮序列長度變化的時候，對于示例數(shù)組{1，4，6，2，8，9，7}來說可以解決，即當序列變長的時候，元素1，4，6，8，9正好是最終的字長遞增子序列；當如果原數(shù)組是{10，9，2，5，3，7，101，18}時，就不是這么回事了。目前我沒有找到求解子序列本身的方法，留作以后思考。）

?

實例二：格子取數(shù)/走棋盤問題

問題描述。給定一個m*n的矩陣，每個位置是一個非負整數(shù)，從左上角開始放一個機器人，它每次只能朝右和下走，走到右下角，求機器人的所有路徑中，總和最小的那條路徑。如下圖所示，其中圖中所示的彩色方塊是已知的某些非負整數(shù)值。

? ? ? ? ? ? ? ? ? ? ? ?

考慮一般情況下位于機器人位于某點(x, y)處，那么它是怎么來的呢？只可能來自于左邊或者上邊。即：

dp[x, y] = min(dp[x-1, y], dp[x, y-1]) + a[x, y],其中a[x, y]是棋盤中(x, y)點的權(quán)重取值。

然后考慮位于最左邊一列與左上邊的一行，得到所有的狀態(tài)轉(zhuǎn)移方程為：

? ? ? ? ? ? ? ? ? ? ? ?

?

所以，代碼如下：

public int minPath(int[][] chess) {int row = chess.length;int col = chess[0].length;int[][] dp = new int[row][col];dp[0][0] = chess[0][0];for(int i=1; i<row; i++) dp[i][0] = dp[i-1][0] + chess[i][0];for(int j=1; j<col; j++)dp[0][j] = dp[0][j-1] + chess[0][j];for(int i=1; i<row; i++) {for(int j=1; j<col; j++) {dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + chess[i][j];}}return dp[row-1][col-1];} View Code

?

觀察狀態(tài)轉(zhuǎn)移方程發(fā)現(xiàn)，每次更新(x, y)，只需要最多知道上一行即可，沒必要知道更早的數(shù)據(jù)。凡是滿足這樣條件的動態(tài)規(guī)劃問題，都可以用“滾動數(shù)組”的方式做空間上的優(yōu)化。

使用滾動數(shù)組的狀態(tài)轉(zhuǎn)移方程如上圖所示。

代碼如下：

public int minPath1(int[][] chess) {int row = chess.length;int col = chess[0].length;int[] dp = new int[col];dp[0] = chess[0][0];for(int j=1; j<col; j++)dp[j] = dp[j-1] + chess[0][j];for(int i=1; i<row; i++) {for(int j=0; j<col; j++) {if(j == 0)dp[j] += chess[i][j];elsedp[j] = (dp[j] < dp[j-1] ? dp[j] : dp[j-1]) + chess[i][j];}}return dp[col-1];} View Code

?

?

實例三：找零錢問題/0-1背包問題

問題描述。給定某不超過100萬元的現(xiàn)金總額，兌換成數(shù)量不限的100、50、20、10、5、2、1元的紙幣組合，共有多少種組合？

思路：此問題涉及兩個類別：面值和總額。所以我們定義dp[i][j]表示使用小于等于i的紙幣，湊成j元錢，共有多少種組合方法。比如dp[100][500]表示使用面值不大于100的紙幣，湊出500塊錢，共有多少種組合方法。

進一步思考，如果面值都是1元的，則無論總額多少，可行的組合數(shù)都為1.比如只用1元的紙幣湊出100元，顯然只有一種組合方法。那么如果多出一種面值呢？組合數(shù)有什么變化？

回到dp[100][500]，既然用小于等于100的紙幣湊出500塊錢，則組合中只會要么包含至少一張100塊的紙幣，要么不包含100塊的紙幣。所以我們可以分成兩種情況考慮：

1）如果沒有包括100元，則用到的最大面值可能為50元，即使用面值小于等于50的紙幣，湊出500塊錢，表示形式為：dp[50][500];

2）如果必須包含100元，怎么計算呢？既然至少包含100元，我們先拿出100塊錢，則還需要湊出400塊錢即可完成。用小于或等于100元的紙幣湊出400塊錢，表示形式為dp[100][400];

將兩者綜合起來為：dp[100][500] = dp[50][500] + dp[100][400];

為了方便表示，我們定義紙幣面值為一個數(shù)組：dom[] = {1,2,5,10,20,50,100},這樣dom[i]和dom[i-1]就表示相鄰的紙幣面額了。i的意義從面值變成了面值下標。

根據(jù)上面分析，對于一般情況，我們有dp[i][j] = dp[i-1][j] + dp[i][j-dom[i]]. ]有了一般情況，在考慮兩種特殊情況：

如果dp[i][0]應該返回啥？dp[i][0]表示用小于等于i的紙幣，湊出0塊錢，我們可以定義這種情況的值為1；

如果dp[0][j]應該返回啥？dp[0][j]表示用小于等于0的紙幣，湊出j塊錢，我們可以定義這種情況的值為1.

再看dp[100][78]，用小于等于100元的紙幣湊出78塊錢，這時組合中一定不會包含100塊的紙幣，因此dp[100][78] = dp[50][78],即當j < dom[i]時，dp[i][j] = dp[i-1][j]。

這樣整個dp的過程就出來了：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?

代碼為：

public int charge(int[] money, int total) {int row = money.length;int col = total + 1;int[][] dp = new int[row][col];for(int j=0; j<col; j++)dp[0][j] = 1; //表示用1塊錢湊出任何金額的組合數(shù)都為1for(int i=1; i<row; i++) {dp[i][0] = 1; for(int j=1; j<col; j++) {if(j < money[i]) //表示要湊出的金額數(shù)小于當前的紙幣面額，如dp[100][87] = dp[50][87]dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j] + dp[i][j-money[i]];}}return dp[row-1][col-1];} View Code

?

?

總結(jié)，什么時候適合用動態(tài)規(guī)劃呢？

? ? ? ? ? ??

? ? ? ? ? ? ?

?

? 總之，動態(tài)規(guī)劃只是一種解決問題的思路，要靈活運用這種方法，多做練習，就能很快找到靈感了。

?

轉(zhuǎn)載于:https://www.cnblogs.com/little-YTMM/p/5372680.html

總結(jié)

以上是生活随笔為你收集整理的详解动态规划——邹博讲动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。