第Python算法思想集結深入理解動態規劃目錄1.概述什么是重疊子問題動態規劃與分治算法的區別什么最優子結構2.流程2.1是否存在子問題2.2是否存在重疊子問題怎么解決重疊子問題2.3狀態轉移3.總結

1.概述

動態規劃算法應用非常之廣泛。

對于算法學習者而言，不跨過動態規劃這道門，不算真正了解算法。

初接觸動態規劃者，理解其思想精髓會存在一定的難度，本文將通過一個案例，抽絲剝繭般和大家聊聊動態規劃。

動態規劃算法有3個重要的概念：

重疊子問題。最優子結構。狀態轉移。

只有吃透這3個概念，才叫真正理解什么是動態規劃。

什么是重疊子問題

動態規劃和分治算法有一個相似之處。

將原問題分解成相似的子問題，在求解的過程中通過子問題的解求出原問題的解。

動態規劃與分治算法的區別

分治算法的每一個子問題具有完全獨立性，只會被計算一次。二分查找是典型的分治算法實現，其子問題是把數列縮小后再二分查找，每一個子問題只會被計算一次。動態規劃經分解得到的子問題往往不是互相獨立的，有些子問題會被重復計算多次，這便是重疊子問題。同一個子問題被計算多次，完全是沒有必要的，可以緩存已經計算過的子問題，再次需要子問題結果時只需要從緩存中獲取便可。這便是動態規劃中的典型操作，優化重疊子問題，通過空間換時間的優化手段提高性能。

重疊子問題并不是動態規劃的專利，重疊子問題是一個很普見的現象。

什么最優子結構

最優子結構是動態規劃的必要條件。因為動態規劃只能應用于具有最優子結構的問題，在解決一個原始問題時，是否能套用動態規劃算法，分析是否存在最優子結構是關鍵。

那么！到底什么是最優子結構？概念其實很簡單，局部最優解能決定全局最優解。

如拔河比賽中。如果A隊中的每一名成員的力氣都是每一個班上最大的，由他們組成的拔河隊毫無疑問，一定是也是所有拔河隊中實力最強的。

如果把求解哪一個團隊的力量最大當成原始問題，則每一個人的力量是否最大就是子問題，則子問題的最優決定了原始問題的最優。

所以，動態規劃多用于求最值的應用場景。

不是說有3個概念嗎！

不急，先把狀態轉移這個概念放一放，稍后再解釋。

2.流程

下面以一個案例的解決過程描述使用動態規劃的流程。

問題描述：小兔子的難題。

有一只小兔子站在一片三角形的胡蘿卜地的入口，如下圖所示，圖中的數字表示每一個坑中胡蘿卜的數量，小兔子每次只能跳到左下角或者右下角的坑中，請問小兔子怎么跳才能得到最多數量的胡蘿卜？

首先這個問題是求最值問題，是否能夠使用動態規劃求解，則需要一步一步分析，看是否有滿足使用動態規劃的條件。

2.1是否存在子問題

先來一個分治思想：思考或觀察是否能把原始問題分解成相似的子問題，把解決問題的希望寄托在子問題上。

那么，針對上述三角形數列，是否存在子問題？

現在從數字7出發，兔子有2條可行路線。

為了便于理解，首先模糊第3行后面的數字或假設第3行之后根本不存在。

那么原始問題就變成：

先分別求解路線1和路線2上的最大值。路線1的最大值為3,路線2上的最大值是8。然后求解出路線1和路線2兩者之間的最大值8。把求得的結果和出發點的數字7相加，7+8=15就是最后答案。只有2行時，兔子能獲得的最多蘿卜數為15，肉眼便能看的出來。

前面是假設第3行之后都不存在，現在把第3行放開，則路線1路線2的最大值就要發生變化，但是，對于原始問題來講，可以不用關心路線1和路線2是怎么獲取到最大值，交給子問題自己處理就可以了。

反正，到時從路線1和路線2的結果中再選擇一個最大值就是。

把第3行放開后，路線1就要重新更新最大值，如上圖所示，路線1也可以分解成子問題，分解后，也只需要關心子問題的返回結果。

路線1的子問題有2個，路線1_1和路線1_2。求解2個子問題的最大值后，再在2個子問題中選擇最大值8，最后路線1的最大值為3+8=11。路線2的子問題有2個，路線2_1和路線2_2。求解2個子問題的最大值后，再在2個子問題中選擇最大值2，最后路線2的最大值為8+2=10。

當第3行放開后，更新路線1和路線2的最大值，對于原始問題而言，它只需要再在2個子問題中選擇最大值11，最終問題的解為7+11=18。

如果放開第4行，將重演上述的過程。和原始問題一樣，都是從一個點出發，求解此點到目標行的最大值。所以說，此問題是存在子問題的。

并且，只要找到子問題的最優解，就能得到最終原始問題的最優解。不僅存在子問題，而且存在最優子結構。

顯然，這很符合遞歸套路：遞進給子問題，回溯子問題的結果。

使用二維數列表保存三角形數列中的所有數據。a=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]。原始問題為f(0，0)從數列的(0,0)出發，向左下角和右下角前行，一直找到此路徑上的數字相加為最大。f(0,0)表示以第1行的第1列數字為起始點。

分解原始問題f(0,0)=a(0,0)+max(f(1,0)+f(1,1))。因為每一個子問題又可以分解，讓表達式更通用f(i,j)=a(i,j)+max(f(i+1,j)+f(i+1,j+1))。(i+1,j)表示(i,j)的左下角，(i+1,j+1)表示(i,j)的右下角，

編碼實現：

#已經數列

nums=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]

#遞歸函數

defget_max_lb(i,j):

ifi==len(nums)-1:

#遞歸出口

returnnums[i][j]

#分解子問題

returnnums[i][j]+max(get_max_lb(i+1,j),get_max_lb(i+1,j+1))

res=get_max_lb(0,0)

print(res)

不是說要聊聊動態規劃的流程嗎！怎么跑到遞歸上去了。

其實所有能套用動態規劃的算法題，都可以使用遞歸實現，因遞歸平時接觸多，從遞歸切入，可能更容易理解。

2.2是否存在重疊子問題

先做一個實驗，增加三角形數的行數，也就是延長路徑線。

importrandom

nums=[]

#遞歸函數

defget_max_lb(i,j):

ifi==len(nums)-1:

returnnums[i][j]

returnnums[i][j]+max(get_max_lb(i+1,j),get_max_lb(i+1,j+1))

#構建100行的二維列表

foriinrange(100):

nums.append([])

forjinrange(i+1):

nums[i].append(random.randint(1,100))

res=get_max_lb(0,0)

print(res)

執行程序后，久久沒有得到結果，甚至會超時。原因何在？如下圖：

路線1_2和路線2_1的起點都是從同一個地方（藍色標注的位置）出發。顯然，從數字1（藍色標注的數字）出發的這條路徑會被計算2次。在上圖中被重復計算的子路徑可不止一條。

**這便是重疊子問題！**子問題被重復計算。

當三角形數列的數據不是很多時，重復計算對整個程序的性能的影響微不足道。如果數據很多時，大量的重復計算會讓計算機性能低下，并可能導致最后崩潰。

因為使用遞歸的時間復雜度為O(2^n)。當數據的行數變多時，可想而知，性能有多低下。

怎么解決重疊子問題

答案是：使用緩存，把曾經計算過的子問題結果緩存起來，當再次需要子問題結果時，直接從緩存中獲取，就沒有必要再次計算。

這里使用字典作為緩存器，以子問題的起始位置為關鍵字，以子問題的結果為值。

importrandom

defget_max_lb(i,j):

ifi==len(nums)-1:

returnnums[i][j]

left_max=None

right_max=None

if(i+1,j)indic.keys():

#檢查緩存中是否存在子問題的結果

left_max=dic[i+1,j]

else:

#緩存中沒有，才遞歸求解

left_max=get_max_lb(i+1,j)

#求解后的結果緩存起來

dic[(i+1,j)]=left_max

if(i+1,j+1)indic.keys():

right_max=dic[i+1,j+1]

else:

right_max=get_max_lb(i+1,j+1)

dic[(i+1,j+1)]=right_max

returnnums[i][j]+max(left_max,right_max)

#已經數列

nums=[]

#緩存器

dic={}

foriinrange(100):

nums.append([])

forjinrange(i+1):

nums[i].append(random.randint(1,100))

#遞歸調用

res=get_max_lb(0,0)

print(res)

因使用隨機數生成數據，每次運行結果不一樣。但是，每次運行后的速度是非常給力的。

當出現重疊子問題時，可以緩存曾經計算過的子問題。

好！現在到了關鍵時刻，屏住呼吸，從分析緩存中的數據開始。

使用遞歸解決問題，從結構上可以看出是從上向下的一種處理機制。所謂從上向下，也就是由原始問題開始一路去尋找答案。從本題來講，就是從第一行一直找到最后一行，或者說從未知找到``已知`。

根據遞歸的特點，可知緩存數據的操作是在回溯過程中發生的。

當再次需要調用某一個子問題時，這時才有可能從緩存中獲取到已經計算出來的結果。緩存中的數據是每一個子問題的結果，如果知道了某一個子問題，就可以通過子問題計算出父問題。

這時，可能就會有一個想法？

從已知找到未知。

任何一條路徑只有到達最后一行后才能知道最后的結果。可以認為，最后一行是已知數據。先緩存最后一行，那么倒數第2行每一個位置到最后一行的路徑的最大值就可以直接求出來。

同理，知道了倒數第2行的每一個位置的路徑最大值，就可以求解出倒數第3行每一個位置上的最大值。以此類推一直到第1行。

天呀！多完美，還用什么遞歸。

可以認為這種思想便是動態規劃的核心：自下向上。

2.3狀態轉移

還差最后一步，就能把前面的遞歸轉換成動態規劃實現。

什么是狀態轉移？

前面分析從最后1開始求最大值過程，是不是有點像田徑場上的多人接力賽跑，第1名運動力爭跑第1，把狀態轉移給第2名運動員，第2名運動員持續保持第1，然后把狀態轉移給第3運動員，第3名運動員也保持他這一圈的第1，一至到最后一名運動員，都保持自己所在那一圈中的第1。很顯然最后結果，他們這個團隊一定是第1名。

把子問題的值傳遞給另一個子問題，這便是狀態轉移。當然在轉移過程中，一定會存在一個表達式，用來計算如何轉移。

用來保存每一個子問題狀態的表稱為dp表，其實就是前面遞歸中的緩存器。

用來計算如何轉移的表達式，稱為狀態轉移方程式。

有了上述的這張表，就可以使用動態規劃自下向上的方式解決兔子的難題這個問題。

nums=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]

#dp列表

dp=[]

idx=0

#從最后一行開始

foriinrange(len(nums)-1,-1,-1):

dp.append([])

forjinrange(len(nums[i])):

ifi==len(nums)-1:

#最后一行緩存于狀態轉移表中

dp[idx].append(nums[i][j])

else:

dp[idx].append(nums[i][j]+max(dp[idx-1][j],dp[idx-1][j+1]))

idx+=1

print(dp)

輸出結果：

[[4,5,2,6,5],[7,12,10,10],[20,13,12],[23,21],[30]]

程序運行后，最終輸出結果和前面手工繪制的dp表中的數據一模一樣。

其實動態規劃實現是前面遞歸操作的逆過程。時間復雜度是O(n^2)。

并不是所有的遞歸操作都可以使用動態規劃進行逆操作，只有符合動態規劃條件的遞歸操作才可以。

上述解決問題時，使用了一個二維列表充當dp表，并保存所有的中間信息。

思考一下，真的有必要保存所有的中間信息嗎？

在狀態轉移過程中，我們僅關心當前得到的狀態信息，曾經的狀態信息其實完全可以不用保存。

所以，上述程序完全可以使用一個一維列表來