《算法設計與分析基礎》（Python語言描述） 課件 第8章動態(tài)規(guī)劃

第8章保存子問題解—動態(tài)規(guī)劃8.1動態(tài)規(guī)劃概述8.2一維動態(tài)規(guī)劃CONTENTS提綱8.3二維動態(tài)規(guī)劃8.4三維動態(tài)規(guī)劃8.5字符串動態(tài)規(guī)劃8.6背包動態(tài)規(guī)劃8.7樹形動態(tài)規(guī)劃8.8區(qū)間動態(tài)規(guī)劃1/918.1動態(tài)規(guī)劃概述動態(tài)規(guī)劃將要解決的問題轉(zhuǎn)化為一系列的子問題并且逐步加以解決，將前面解決子問題的結(jié)果作為后續(xù)解決子問題的條件，并且避免無意義的窮舉。說明2/918.1.1從一個簡單示例入門【例8-1】一個樓梯有n（1≤n≤100）個臺階，上樓可以一步上1個臺階，也可以一步上2個臺階，設計一個算法求上樓梯共有多少種不同的走法。3/91解設f(n)表示上n個臺階的樓梯的走法數(shù)，顯然，f(1)=1，f(2)=2（一種走法是一步上1個臺階、走2步，另外一種走法是一步上2個臺階）。對于大于2的n個臺階的樓梯：一種走法是第一步上1個臺階，剩余n-1個臺階的走法數(shù)是f(n-1)；另外一種走法是第一步上2個臺階，剩余n-2個臺階的走法數(shù)是f(n-2)。所以有

f(n)=f(n-2)+f(n-1)。對應的遞歸模型如下：f(1)=1f(2)=2f(n)=f(n-2)+f(n-1) n>24/911 deff1(n): #算法12 ifn==1:return13 elifn==2:return24 else:returnf1(n-2)+f1(n-1)f1(5)f1(3)f1(4)f1(1)f1(2)f1(3)f1(1)f1(2)f1(2)存在大量重復的子問題5/911 deff21(n): #被f2調(diào)用2 ifdp[n]!=0:returndp[n]3 ifn==1:dp[n]=14 elifn==2:dp[n]=25 else:dp[n]=f21(n-2)+f21(n-1)6 returndp[n]78 deff2(n): #算法29 globaldp10 dp=[0]*10511 returnf21(n)如何避免重疊子問題的重復計算呢？可以設計一個一維dp數(shù)組，用dp[i]存放f1(i)的值。遞歸算法6/91上述算法2采用遞歸算法，可以直接采用迭代實現(xiàn)，仍然設計一維dp數(shù)組，用dp[i]存放f1(i)的值。1 deff3(n): #算法32 dp=[0]*105 #假設n的最大值不超過1053 dp[1]=14 dp[2]=25 foriinrange(3,n+1):6 dp[i]=dp[i-2]+dp[i-1]7 returndp[n]迭代算法7/91上述算法3就是動態(tài)規(guī)劃算法，其中數(shù)組dp（表）稱為動態(tài)規(guī)劃數(shù)組，從中看出動態(tài)規(guī)劃就是記錄子問題的結(jié)果再利用的方法。原問題子問題1子問題2子問題k…表原問題的解8/91f(1)f(n-2)f(n-1)f(n)…f(n)=f(n-2)+f(n-1)1 deff4(n): #算法42 dp=[0]*33 dp[0],dp[1]=1,24 foriinrange(2,n):5 dp[i%3]=dp[(i-1)%3]+dp[(i-2)%3]6 returndp[(n-1)%3]f(i)的值存放在dp[i-1]中滾動數(shù)組9/91最常見的算法1 deff5(n): #算法52 ifn==1:return13 elifn==2:return24 else:5 a,b,c=1,2,06 foriinrange(3,n+1):7 c=a+b8 a,b=b,c9 returnc10/918.1.2動態(tài)規(guī)劃的原理一個多段圖G=（V，E），在頂點0處有一水庫，現(xiàn)需要從頂點0鋪設一條管道到頂點9，邊上的數(shù)字表示對應兩個頂點之間的距離，該圖采用鄰接矩陣A表示。現(xiàn)要找出一條從頂點0到頂點9的線路，使得鋪設的管道長度最短。5343343633474236242012345678911/9153433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}分為5個階段，通常階段變量用k表示，這里k為0～4。階段k可能有多個狀態(tài)，通常用狀態(tài)集合Sk表示，例如S1={1，2，3}。狀態(tài)變量xk表示Sk中某個狀態(tài)，如x1可以取S1中的任意值。12/91動態(tài)規(guī)劃中當前階段的狀態(tài)往往是上一階段狀態(tài)和相應決策的結(jié)果，采用指標函數(shù)表示它們之間關系稱為狀態(tài)轉(zhuǎn)移方程，指標函數(shù)通常是最優(yōu)解函數(shù)。設最優(yōu)解函數(shù)f(s)為狀態(tài)s到終點9的最短路徑長度，用k表示階段。13/91狀態(tài)轉(zhuǎn)移方程：53433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}f4(9)=0fk(s)=min<s,t>∈E{A[s][t]+fk+1(t)} k從3到014/91從k=3開始直到k=0為止，f0(0)就是最短管道長度，稱為逆序解法。f4(9)=0fk(s)=min<s,t>∈E{A[s][t]+fk+1(t)} k從3到053433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}15/91逆序解法過程f4(9)=0f3(7)=A[7][9]+f4(9)=3f3(8)=A[8][9]+f4(9)=453433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}34016/91f2(4)=min(A[4][7]+f3(7)=6,A[4][8]+f3(8)=8)=6f2(5)=min(A[5][7]+f2(7)=9,A[5][8]+f2(8)=7)=7f2(6)=min(A[6][7]+f3(7)=6,A[6][8]+f2(8)=7)=653433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}6763417/91f1(1)=min(A[1][4]+f2(4)=13,A[1][5]+f2(5)=11)=11f1(2)=min(A[2][4]+f2(4)=9,A[2][5]+f2(5)=9,A[2][6]+f2(6)=10)=9f1(3)=min(A[3][4]+f2(4)=12,A[3][5]+f2(5)=9,A[3][6]+f2(6)=11)=953433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}676119918/91f0(0)=min(A[0][1]+f1(4)=13,A[0][2]+f1(2)=13,A[0][3]+f0(3)=12)=1253433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}11991219/91也可以設最優(yōu)解函數(shù)f(s)為起點0到狀態(tài)s的最短路徑長度狀態(tài)轉(zhuǎn)移方程：f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k從1到420/9153433436334742362420123456789108758243012這樣求解過程是從k=1開始直到k=4為止，f4(9)就是最短管道長度，稱為順序解法。f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k從1到421/918.1.3動態(tài)規(guī)劃求解問題的性質(zhì)和步驟最優(yōu)子結(jié)構：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構性質(zhì)，即滿足最優(yōu)性原理。無后效性：如果某個階段狀態(tài)一旦確定，就不受以后決策的影響，也就是說某個狀態(tài)以后的決策不會影響以前的狀態(tài)。重疊子問題：一個問題分解的若干子問題之間是不獨立的，其中一些子問題在后面的決策中可能被多次重復使用。該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。采用動態(tài)規(guī)劃求解的問題一般要具有以下3個性質(zhì)22/91確定狀態(tài)：將問題求解中各個階段所處的各種情況用不同的狀態(tài)表示出來。確定狀態(tài)轉(zhuǎn)移方程：描述求解中各個階段的狀態(tài)轉(zhuǎn)移和指標函數(shù)的關系。確定初始條件和邊界情況：狀態(tài)轉(zhuǎn)移方程通常是一個遞推式，初始條件通常指定遞推的起點，在遞推中需要考慮一些特殊情況，稱為邊界情況。確定計算順序：也就是指定求狀態(tài)轉(zhuǎn)移方程的順序，是順序求解還是逆序求解。消除冗余：如采用滾動數(shù)組進一步提高時空性能。一般來說動態(tài)規(guī)劃算法設計要經(jīng)歷以下幾個步驟23/918.1.4動態(tài)規(guī)劃與其他方法的比較動態(tài)規(guī)劃的基本思想與分治法類似，也是將求解的問題分解為若干個子問題（階段），按照一定的順序求解子問題，前一個子問題的解有助于后一個子問題的求解。但分治法中各個子問題是獨立的（不重疊），而動態(tài)規(guī)劃適用于子問題重疊的情況。動態(tài)規(guī)劃又和貪心法有些相似，都需要滿足最優(yōu)子結(jié)構性質(zhì)，都是將一個問題的解決方案視為一系列決策的結(jié)果。不同的是貪心法每次采用貪心選擇便做出一個不可回溯的決策，而動態(tài)規(guī)劃算法中隱含有回溯的過程。24/918.2一維動態(tài)規(guī)劃一維動態(tài)規(guī)劃是指設計動態(tài)規(guī)劃算法中采用一維動態(tài)規(guī)劃數(shù)組，也稱為線性動態(tài)規(guī)劃。說明25/91給定一個含n（n≥1）個整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。序列（-2，11，-4，13，-5，-2）的最大連續(xù)子序列和為20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大連續(xù)子序列和為16。規(guī)定一個序列最大連續(xù)子序列和至少是0，如果小于0，其結(jié)果為0。8.2.1最大連續(xù)子序列和26/91解dp[0]=a[0] 初始條件dp[i]=max(dp[i-1]+ai，ai) i>0

設計一維動態(tài)規(guī)劃dp，dp[i]（0≤i≤n-1）表示以元素ai結(jié)尾的最大連續(xù)子序列和，顯然dp[i-1]表示以元素ai-1結(jié)尾的最大連續(xù)子序列和。判斷ai分為兩種情況：將ai合并到前面以元素ai-1結(jié)尾的最大連續(xù)子序列中，此時有dp[i]=dp[i-1]+ai。不將ai合并到前面以元素ai-1結(jié)尾的最大連續(xù)子序列中，即從ai開始構造一個連續(xù)子序列，此時有dp[i]=ai。27/91dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2ans=dp[3]=20max求出dp中的最大元素ans。由于本題中最大連續(xù)子序列和至少為0（或者說最大連續(xù)子序列可以為空序列），所以最后的最大連續(xù)子序列和應該為max(ans，0)。28/911 defmaxSubSum(a): #求最大連續(xù)子序列和2 globaldp3 n=len(a)4 dp=[0]*n5 dp[0]=a[0]6 foriinrange(1,n):7 dp[i]=max(dp[i-1]+a[i],a[i])8 ans=max(dp) #求dp中最大元素9 returnmax(ans,0)【算法分析】maxSubSum算法時間復雜度均為O(n)，空間復雜度為O(n)。29/91先在dp數(shù)組中求出最大元素的序號maxi，i從maxi序號開始在a中向前查找，rsum從dp[maxi]開始遞減a[i]，直到rsum為0，對應的a中子序列就是一個最大連續(xù)子序列。dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2i=maxi=3rsum=7i=2rsum=11i=1rsum=0逆置max{11，-4，13}求出dp后推導出一個最大連續(xù)子序列30/911 defmaxSub(a): #求一個最大連續(xù)子序列2 n=len(a)3 x=[] #存放一個最大連續(xù)子序列4 maxi=dp.index(max(dp)) #求最大dp元素下標5 rsum=dp[maxi]6 i=maxi7 whilei>=0andrsum!=0:8 rsum-=a[i]9 x.append(a[i])10 i-=111 x.reverse()12 returnx31/91空間優(yōu)化如果只需要求最大連續(xù)子序列和，可以采用滾動數(shù)組優(yōu)化空間。maxSubSum算法中用j標識階段，由于dp[j]僅僅與dp[j-1]相關，將一維dp數(shù)組改為單個變量dp。1 defmaxSubSum1(a): #求最大連續(xù)子序列和2 n=len(a)3 ifn==1:returna[0]4 dp=a[0]5 ans=dp6 forjinrange(1,n):7 dp=max(dp+a[j],a[j])8 ans=max(ans,dp)9 returnmax(ans,0)空間復雜度為O(1)32/91問題描述:給定一個含n（1≤n≤30000）個整數(shù)的數(shù)組

nums（整數(shù)值在-100000到100000之間），找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

例如nums={-2,-1}，結(jié)果為-1。

要求設計如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int:8.2.2實戰(zhàn)—最大子序和（LeetCode53★）33/91解本題采用動態(tài)規(guī)劃求解的原理見8.2.1節(jié)，這里僅僅需要求最大連續(xù)子序列和，而且該最大連續(xù)子序列至少含一個元素。采用滾動數(shù)組。1 class

Solution:2

def

maxSubArray(self,

nums:

List[int])

->

int:3

n=len(nums)4

if

n==1:return

nums[0]5

dp=nums[0]6

ans=dp7

for

j

in

range(1,n):8

dp=max(dp+nums[j],nums[j])9

ans=max(ans,dp)10

return

ans

#不能改為max(ans,0)34/91上述程序提交時通過，執(zhí)行用時為172ms，內(nèi)存消耗為30MB。35/91問題描述：給定一個無序的整數(shù)序列a[0..n-1]，求其中最長遞增（嚴格）子序列的長度。例如，a={2，1，5，3，6，4，8，9，7}，n=9，其最長遞增子序列為{1，3，4，8，9}，結(jié)果為5。8.2.3最長遞增子序列36/91解dp[i]表示以a[i]結(jié)尾的最長遞增子序列的長度。計算順序是i從0到n-1，對于每個a[i]，dp[i]置為1（表示只有a[i]一個元素時最長遞增子序列的長度為1）。37/91考慮a[0..i-1]中的每一個元素a[j]，分為兩種情況：若a[j]<a[i]，則以aj結(jié)尾的最長遞增子序列加上ai可能構成一個更長的遞增子序列，此時有dp[i]=max(dp[i]，dp[j]+1)。a0

…

aj

…

ai-1

ai

…

an-1dp[j]dp[i]=max(dp[i],dp[j]+1)aj<ai否則最長遞增子序列沒有改變。在求出dp數(shù)組后，通過順序遍歷dp求出最大值ans，則ans就是最長遞增（嚴格）子序列的長度。38/91狀態(tài)轉(zhuǎn)移方程dp[i]=1 0≤i≤n-1（初始條件）dp[i]=maxa[j]<a[i](j<i){dp[j]+1} 0≤i≤n-139/911 defmaxInclen(a): #求最長遞增子序列長度2 globaldp3 n=len(a)4 dp=[0]*n5 foriinrange(0,n):6 dp[i]=17 forjinrange(0,i):8 ifa[i]>a[j]:dp[i]=max(dp[i],dp[j]+1)9 ans=max(dp) #求dp中最大元素10 returnans【算法分析】時間復雜度為O(n2)，空間復雜度為O(n)。40/91當求出dp后可以推導出一個最長遞增子序列。先在dp數(shù)組中求出最大元素的序號maxj，置j=maxj，prej從j的前一個序號開始在a中向前查找，rnum從dp[maxj]開始，若a[prej]<a[j]置rnum--，直到rnum為0，對應的a中子序列就是一個最大連續(xù)子序列。a0

…

aj

…

ai-1

ai

…

an-1maxjdp[i]=max(dp[i],dp[[j]+1)aj<ai41/911 defmaxInc(a): #求一個最長遞增子序列2 n,x=len(a),[] #x存放一個最長遞增子序列3 maxj=dp.index(max(dp)) #dp中最大元素下標4 rnum=dp[maxj] #剩余的元素個數(shù)5 j=maxj #j指向當前最長遞增子序列的元素6 x.append(a[j])7 prej=maxj-1 #prej查找前一個元素8 whileprej>=0andrnum!=0:9 ifa[prej]<a[j]anddp[prej]==rnum-1:10 rnum-=111 x.append(a[prej])12 j=prej;prej-=113 x.reverse() #逆置x14 returnx42/91假設有n個活動和一個資源，每個活動執(zhí)行時都要占用該資源，并且該資源任何時刻只能被一個活動所占用，一旦某個活動開始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。每個活動i有一個開始時間bi和結(jié)束時間ei（bi<ei），它是一個半開時間區(qū)間[bi，ei），其占用資源的時間=ei-bi。假設最早活動執(zhí)行時間為0。求一種最優(yōu)活動安排方案，使得安排的活動的總占用時間最長。8.2.4*活動安排問題Ⅱ43/91解該問題與7.2.1節(jié)的活動安排問題Ⅰ類似，不同的是這里求一個總占用時間最長的兼容活動子集，而不是求活動個數(shù)最多的兼容活動子集，兩者是不同的。這里采用貪心法+動態(tài)規(guī)劃的思路，先求出每個活動A[i]的占用資源的時間A[i].length=A[i].e-A[i].b，將活動數(shù)組A[0..n-1]按結(jié)束時間遞增排序（貪心思路）。44/9111個活動（已按結(jié)束時間的遞增排列）活動i012345678910開始時間130535688212結(jié)束時間4567891011121315ans=1345/91設計一維動態(tài)規(guī)劃數(shù)組dp，dp[i]表示A[0..i]（共i+1個活動）中所有兼容活動的最長占用時間?？紤]活動i，找到前面與之兼容的最晚的活動j，即，稱活動j為活動i的前驅(qū)活動。如果活動i找到了前驅(qū)活動j，可以有兩種選擇：①活動j之后不選擇活動i，此時dp[i]=dp[i-1]。②活動j之后選擇活動i，此時dp[i]=dp[j]+A[i].length。兩種情況中取最大值。對應的狀態(tài)轉(zhuǎn)移方程如下：dp[0]=活動0的時間

邊界情況dp[i]=max{dp[i-1]，dp[j]+A[i].length} 活動j是活動i的前驅(qū)46/91

求出dp數(shù)組后，dp[n-1]就是最長的總占用時間。為了求一個最優(yōu)安排方案，設計一個一維數(shù)組pre，pre[i]的含義如下：①若活動i沒有前驅(qū)活動，置pre[i]=-2。②若活動i有前驅(qū)活動j，但不選擇活動i，置pre[i]=-1。③若活動i有前驅(qū)活動j，選擇活動i，置pre[i]=j。47/911 classAction: #活動類2 def__init__(self,b,e):3 self.b=b #活動起始時間4 self.e=e #活動結(jié)束時間5 self.length=e-b #求每個活動的占用時間6 def__lt__(self,other): #用于按e遞增排序7 ifself.e<other.e:returnTrue8 else:returnFalse48/9110 defplan(A): #動態(tài)規(guī)劃算法求dp11 globaldp,pre12 n=len(A)13 dp=[0]*n #初始化dp元素為014 pre=[-5]*n15 A.sort() #按e遞增排序16 dp[0]=A[0].length17 pre[0]=-2 #活動0沒有前驅(qū)活動49/9118 foriinrange(1,n):19 j=i-120 whilej>=0andA[j].e>A[i].b:j-=1

#找活動i的前驅(qū)j21 ifj==-1: #活動i前面沒有兼容22 dp[i]=A[i].length23 pre[i]=-2 #活動i沒有前驅(qū)24 else: #活動i存在前驅(qū)j25 ifdp[i-1]>dp[j]+A[i].length:26 dp[i]=dp[i-1]27 pre[i]=-1 #不選擇活動i28 else:29 dp[i]=dp[j]+A[i].length30 pre[i]=j #選活動i,前驅(qū)為j31 returndp[n-1]50/91【算法分析】主要時間花費在查找前驅(qū)活動上，對應的時間復雜度為O(n2)。51/911 defgetx(n): #求一個最優(yōu)方案2 x=[] #存放一個方案3 i=n-1 #從n-1開始4 whileTrue:5 ifi==-2:break #已經(jīng)沒有前驅(qū)活動了6 ifpre[i]==-1:i-=1 #不選擇活動i7 else: #選擇活動i8 x.append(i)9 i=pre[i]10 x.reverse() #逆置x11 returnx52/9111個活動求出的dp和pre如下所示。dp[10]=13活動i012345678910開始時間130535688212結(jié)束時間4567891011121315length326254434113dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-2853/91求一個最優(yōu)安排方案x活動i012345678910dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-28i=n-1=10pre[10]=8活動10√

xi=pre[10]=8pre[8]=-1活動8×i減1

i=7pre[7]=-1活動7×

i減1

i=6pre[6]=2活動6√

xi=pre[6]=2pre[2]=-2活動2√

xi=pre[2]=-2i=-2說明沒有前驅(qū)活動，結(jié)束x={2,6,10}1354/918.3二維動態(tài)規(guī)劃二維動態(tài)規(guī)劃是指設計動態(tài)規(guī)劃算法中采用二維動態(tài)規(guī)劃數(shù)組，也稱為坐標型動態(tài)規(guī)劃。說明55/91給定一個高度為n的整數(shù)三角形，求從頂部到底部的最小路徑和及其一條最小路徑，從每個整數(shù)出發(fā)只能向下移動到相鄰的整數(shù)。例如，一個n=4的三角形，輸出的最小路徑和是13，一條最小路徑是2，3，5，3。23472659838.3.1三角形最小路徑和56/91解問題求解—自頂向下2347265983i-1,ji-1,j-1i,jJI234726598357/91

設計數(shù)組dp，dp[i][j]表示從頂部a[0][0]到達（i，j）位置的最小路徑和。起始位置只有（0，0），所以初始化為dp[0][0]=a[0][0]。這里有如下兩個邊界：對于j=0即第0列的任意位置（i，0），只有垂直方向到達的一條路徑，此時有dp[i][0]=dp[i-1][0]+a[i][0]。對于i=j即對角線上的任意位置（i，i），只有左斜方向到達的一條路徑，此時有dp[i][i]=dp[i-1][i-1]+a[i][i]。

234726598358/91其他兩條到達（i，j）位置的路徑，最小路徑和

dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]。i-1,ji-1,j-1i,jJI59/91dp[0][0]=a[0][0] 初始條件dp[i][0]=dp[i-1][0]+a[i][0] 第0列的邊界情況，1≤i≤n-1dp[i][i]=dp[i-1][i-1]+a[i][i] 對角線的邊界情況，1≤i≤n-1dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]

i>1的其他有兩條達到路徑在dp數(shù)組的第n-1行中求出的最小元素ans=dp[n-1][minj]。60/911 defminPathSum(a): #自頂向下求最小路徑和2 n=len(a)3 dp=[[0]*nforiinrange(n)] #二維動態(tài)規(guī)劃數(shù)組4 dp[0][0]=a[0][0]5 foriinrange(1,n): #考慮第0列的邊界6 dp[i][0]=dp[i-1][0]+a[i][0]7 foriinrange(1,n): #考慮對角線的邊界8 dp[i][i]=a[i][i]+dp[i-1][i-1]9 foriinrange(2,n): #考慮其他有兩條達到路徑的結(jié)點10 forjinrange(1,i):11 dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+a[i][j]12 ans=min(dp[n-1]) #求出dp[n-1]中最小元素ans13 returnans61/91那么如何找到一條最小和的路徑呢？設計一個二維數(shù)組pre，pre[i][j]表示到達（i，j）位置時最小路徑上的前驅(qū)位置，由于前驅(qū)位置只有兩個即（i-1，j-1）和（i-1，j），用pre[i][j]記錄前驅(qū)位置的列號即可。i-1,ji-1,j-1i，jpre[i][j]=j-1i-1,ji-1,j-1i，jpre[i][j]=j在求出ans后，通過pre[n-1][minj]推導求出反向路徑path，逆向輸出得到一條最小和的路徑。62/911 defminPathSum1(a): #求最小路徑和以及一條最小和路徑2 n=len(a)3 dp=[[0]*nforiinrange(n)] #二維動態(tài)規(guī)劃數(shù)組4 pre=[[0]*nforiinrange(n)] #二維路徑數(shù)組5 dp[0][0]=a[0][0]6 foriinrange(1,n): #考慮第0列的邊界7 dp[i][0]=dp[i-1][0]+a[i][0]8 pre[i][0]=09 foriinrange(1,n): #考慮對角線的邊界10 dp[i][i]=a[i][i]+dp[i-1][i-1]11 pre[i][i]=i-1i-1,0i,0pre[i][j]=0i-1,i-1i，ipre[i][i]=i-163/9112 foriinrange(2,n): #兩條達到路徑的結(jié)點13 forjinrange(1,i):14 ifdp[i-1][j-1]<dp[i-1][j]:15 dp[i][j]=a[i][j]+dp[i-1][j-1]16 pre[i][j]=j-117 else:18 dp[i][j]=a[i][j]+dp[i-1][j]19 pre[i][j]=ji-1,ji-1,j-1i，jpre[i][j]=j-1i-1,ji-1,j-1i，jpre[i][j]=j64/9120 ans,minj=min(dp[n-1]),dp[n-1].index(min(dp[n-1]))

#求出dp[n-1]中最小ans和對應列號minj21 print("最小路徑和ans=",ans)22 i=n-123 path=[] #存放一條路徑24 whilei>=0

#從(n-1,minj)反推反向路徑25 path.append(a[i][minj])26 minj=pre[i][minj] #最小路徑在上一行中的列號27 i-=1

#在前一行查找28 path.reverse() #逆置path29 print("一條最小路徑:",path)65/91問題求解—自底向上i+1,j+1i+1,ji，

jJI234726598366/91

設計二維動態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]表示從底部到達（i，j）位置的最小路徑和。起始位置（n-1，*），所以初始化為dp[n-1][j]=a[n-1][j]。同樣有如下兩個邊界：對于j=0即第0列的任意位置（i，0），只有垂直方向到達的一條路徑，此時有dp[i][0]=dp[i+1][0]+a[i][0]。對于i=j即對角線上的任意位置（i，i），只有左斜方向到達的一條路徑，此時有dp[i][i]=dp[i+1][i+1]+a[i][i]。

234726598367/91其他兩條到達（i，j）位置的路徑，最小路徑和

dp[i][j]=min(dp[i+1][j+1]，dp[i+1][j])+a[i][j]。i+1,j+1i+1,ji，

jJI68/91dp[n-1][j]=a[n-1][j] 初始條件dp[i][0]=dp[i+1][0]+a[i][0] 第0列的邊界情況，0≤i≤n-2dp[i][i]=dp[i+1][i+1]+a[i][i] 對角線的邊界情況，0≤i≤n-2dp[i][j]=min(dp[i+1][j]，dp[i+1][j+1])+a[i][j]

i<n-1兩條達到路徑由于第0行只有一個元素，所以dp[0][0]就是最終的最小路徑和。69/911 defminPathSum2(a): #自底向上求最小路徑和2 n=len(a)3 dp=[[0]*nforiinrange(n)] #二維動態(tài)規(guī)劃數(shù)組4 forjinrange(0,n):5 dp[n-1][j]=a[n-1][j]

#第n-1行6 foriinrange(n-2,-1,-1): #考慮第0列的邊界7 dp[i][0]=dp[i+1][0]+a[i][0]8 foriinrange(n-2,-1,-1): #考慮對角線的邊界9 dp[i][i]=a[i][i]+dp[i+1][i+1]10 foriinrange(n-2,-1,-1): #考慮有兩條達到的路徑11 forjinrange(0,len(a[i])):12 dp[i][j]=min(dp[i+1][j+1],dp[i+1][j])+a[i][j]13 returndp[0][0]70/91自底向上算法空間優(yōu)化在自底向上算法中階段i（指求第i行的dp）僅僅與階段i+1相關，采用降維滾動數(shù)組方式，將dp由二維數(shù)組改為一維數(shù)組。dp[*][j]dp[j]i+1,j+1i+1,ji，

jJI234726598371/911 defminPathSum3(a): #自底向上的優(yōu)化算法2 n=len(a)3 dp=[0]*n #一維動態(tài)規(guī)劃數(shù)組4 foriinrange(n-1,-1,-1):5 forjinrange(0,len(a[i])):6 ifj<len(a)-1:7 dp[j]=min(dp[j],dp[j+1])+a[i][j]8 else:9 dp[j]+=a[i][j]10 returndp[0]10 foriinrange(n-2,-1,-1): #考慮有兩條達到的路徑11 forjinrange(0,len(a[i])):12 dp[i][j]=min(dp[i+1][j+1],dp[i+1][j])+a[i][j]72/918.3.2實戰(zhàn)—下降路徑最小和（LeetCode931★★）問題描述：給定一個n×n的整數(shù)數(shù)組

matrix，找出并返回通過matrix的下降路徑的最小和。下降路徑可以從第一行中的任何元素開始，并從每一行中選擇一個元素。在下一行選擇的元素和當前行所選元素最多相隔一列（即位于正下方或者沿對角線向左或者向右的第一個元素）。具體來說，位置（i，j）的下一個元素應當是（i+1，j-1）、（i+1，j）或者（i+1，j+1）。

例如，matrix={{2，1，3}，{6，5，4}，{7，8，9}}，答案是13。231645798(a)路徑1231645798(b)路徑273/91解問題求解—自上而下dp[i][j]表示從第0行開始并且以（i，j）位置為終點的下降路徑中最小路徑和。采用自上而下的方式求dp。到達（i，j）位置的路徑有3條。i-1,ji，ji-1,j-1i-1,j+1min74/91第0行：dp[0][j]=matrix[0][j]。一般情況：

dp[i][j]=min3(dp[i-1][j-1]，dp[i-1][j]，

dp[i-1][j+1])+matrix[i][j]231645798i-1,ji，ji-1,j-1i-1,j+1min75/91考慮邊界情況如下：①當j=0時有：

dp[i][j]=min(dp[i-1][j]，dp[i-1][j+1])+matrix[i][j]。②當j=n-1時有：

dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+matrix[i][j]。上述各式合起來構成狀態(tài)轉(zhuǎn)移方程，由其求出dp數(shù)組，那么dp中第n-1

行的最小值就是第0行開始到第n-1行的下降路徑中最小路徑和。76/911 class

Solution:2

def

minFallingPathSum(self,

matrix)

->

int:3

n=len(matrix)4

if

n==1:return

matrix[0][0]

#n=1為特殊情況5

dp=[[0]*n

for

i

in

range(n)]

#二維動態(tài)規(guī)劃數(shù)組6

for

j

in

range(0,n):

#第0行:邊界情況7

dp[0][j]=matrix[0][j]77/918

for

i

in

range(1,n):9

for

j

in

range(0,n):10

if

j==0:dp[i][j]=min(dp[i-1][j], dp[i-1][j+1])+matrix[i][j]11

elif

j==n-1:dp[i][j]=min(dp[i-1][j-1], dp[i-1][j])+matrix[i][j]12

else:dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j],dp[i-1][j+1]))+matrix[i][j]13

ans=min(dp[n-1])

#求dp第n-1行中的最小元素ans14

return

ans78/91自上而下算法空間優(yōu)化由于dp[i]僅僅與dp[i-1]相關，采用滾動數(shù)組方法，將dp數(shù)組大小改為dp[2][n]：用dp[0][j]存放dp[i-1][j]，用dp[1][j]存放dp[i][j]。通過變量c實現(xiàn)dp[0]和dp[1]之間的切換。79/911 class

Solution:2

def

minFallingPathSum(self,matrix)

->

int:3

n=len(matrix)4

if

n==1:return

matrix[0][0]

#n=1為特殊情況5

dp=[[0]*n

for

i

in

range(2)]

#二維動態(tài)規(guī)劃數(shù)組80/916

for

j

in

range(0,n):

#第0行:邊界情況7

dp[0][j]=matrix[0][j]8

c=09

for

i

in

range(1,n):10

c=1-c11

for

j

in

range(0,n):12

if

j==0:dp[c][j]=min(dp[1-c][j], dp[1-c][j+1])+matrix[i][j]13

elif

j==n-1:dp[c][j]=min(dp[1-c][j-1], dp[1-c][j])+matrix[i][j]14

else:dp[c][j]=min(dp[1-c][j-1], min(dp[1-c][j],dp[1-c][j+1]))+matrix[i][j]15

ans=min(dp[c])

#求dp第c行中的最小元素ans16

return

ans81/91上述代碼提交時通過，執(zhí)行用時為56ms，內(nèi)存消耗為15.8MB。自下而上的動態(tài)規(guī)劃算法自學82/918.4三維動態(tài)規(guī)劃三維動態(tài)規(guī)劃是指設計動態(tài)規(guī)劃算法中采用三維動態(tài)規(guī)劃數(shù)組。說明83/91設計二維數(shù)組B存放當前頂點之間的最短路徑長度，其中B[i][j]表示當前頂點i到j的最短路徑長度。依頂點編號順序處理每個頂點，每個頂點的處理看作一個階段，階段k（0≤k≤n-1）的結(jié)果存放在Bk中，Bk[i][j]表示處理完0～k的頂點后得到的頂點i到j的最短路徑長度。求一個帶權圖中任意兩個頂點之間的最短路徑長度。8.4.1Floyd算法84/91階段k的處理過程：Bk-1[i][k]Bk-1[k][j]ijkBk-1[i][j]路徑①路徑②B-1[i][j]=A[i][j]Bk[i][j]=min0≤k≤n-1{Bk-1[i][j]，Bk-1[i][k]+Bk-1[k][j]}85/911 defFloyd1(A): #Floyd算法3 n=len(A)4 dp=[[[INF]*nforiinrange(n)]forjinrange(n+1)]5 foriinrange(0,n): #求B(-1)6 forjinrange(0,n):7 dp[0][i][j]=A[i][j]8 forkinrange(1,n+1): #依次求B(0)到B(n-1)9 foriinrange(0,n):10 forjinrange(0,n):11 dp[k][i][j]=min(dp[k-1][i][j], dp[k-1][i][k-1]+dp[k-1][k-1][j])B-1[i][j]=A[i][j]Bk[i][j]=min0≤k≤n-1{Bk-1[i][j]，Bk-1[i][k]+Bk-1[k][j]}86/91階段k僅僅與階段k-1相關，因此可以將dp滾動為dp[2][MAXN][MAXN]。階段k中求dp[k][i][j]時i和j的任意順序不影響最后的結(jié)果，進一步將dp[2][MAXN][MAXN]滾動為二維數(shù)組dp[MAXN][MAXN]?？臻g優(yōu)化87/91從狀態(tài)轉(zhuǎn)移方程可以推出如下關系（其中dp[*][k][k]=0）：dp[k][i][k]=min{dp[k-1][i][k]，dp[k-1][i][k]+dp[k-1][k][k]} =dp[k-1][i][k]dp[k][k][j]=min{dp[k-1][k][j]，dp[k-1][k][k]+dp[k-1][k][j]}=dp[k-1][k][j]在迭代為k時dp[k][i][j]僅僅根據(jù)自己的值以及dp[k-1][i][k]和dp[k-1][k][j]的值計算得出。而dp[k-1][i][k]和dp[k-1][k][j]在階段k中不變，所以可以將dp數(shù)組由三維降為二維。原因解釋：dp[k][i][j]=min0≤k≤n-1{dp[k-1][i][j]，dp[k-1][i][k]+dp[k-1][k][j]}88/911 defFloyd(A):2 globaldp3 n=len(A)4 dp=[[INF]*nforiinrange(n)] #二維動態(tài)規(guī)劃數(shù)組5 foriinrange(0,n): #求B(-1)6 forjinrange(0,n):7 dp[i][j]=A[i][j]8 forkinrange(0,n): #依次求B(0)到B(n-1)9 foriinrange(0,n):10 forjinrange(0,n):11 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])89/918.4.2*雙機調(diào)度問題用兩臺處理機MA和MB加工n個作業(yè)，作業(yè)的編號為0～n-1，兩臺機器均可以加工任何作業(yè)。第i個作業(yè)單獨交給MA時的加工時間是a[i]，單獨交給MB時的加工時間是b[i]?，F(xiàn)在要求每個作業(yè)只能由一臺機器加工，但兩臺機器在任何時刻可以加工兩個不同的作業(yè)。設計一個動態(tài)規(guī)劃算法，使得兩臺機器加工完所有n個作業(yè)的最短時間（從任何一臺機器開工到最后一臺機器停工的總時間）。例如，n=6，a

為（2，5，7，10，5，2），b為（3，8，4，11，3，4），結(jié)果為15。90/91解三維動態(tài)規(guī)劃數(shù)組一維動態(tài)規(guī)劃數(shù)組自學91/918.1動態(tài)規(guī)劃概述8.2一維動態(tài)規(guī)劃CONTENTS提綱8.3二維動態(tài)規(guī)劃8.4三維動態(tài)規(guī)劃8.5字符串動態(tài)規(guī)劃8.6背包動態(tài)規(guī)劃8.7樹形動態(tài)規(guī)劃8.8區(qū)間動態(tài)規(guī)劃第8章保存子問題解—動態(tài)規(guī)劃92/878.5字符串動態(tài)規(guī)劃字符串動態(tài)規(guī)劃是指采用動態(tài)規(guī)劃算法求解字符串的相關問題。說明93/87一個字符串的子序列是指從該字符串中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。給定兩個字符串a(chǎn)和b，稱字符串c是a和b的公共子序列，是指c同是a和b的子序列。該問題是求兩個字符串a(chǎn)和b的最長公共子序列（LCS）。8.5.1最長公共子序列問題94/87設計二維動態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]為（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長公共子序列長度，求dp[i][j]的兩種情況。解a0

a1

…

ai-2

ai-1(a)ai-1=bj-1b0

b1

…

bj-2

bj-1dp[i-1][j-1]dp[i][j]=dp[i-1][j-1]+1a0

a1

…

ai-2

ai-1(b)ai-1≠bj-1b0

b1

…

bj-2

bj-1dp[i][j-1]dp[i][j]=max(dp[i][j-1]，dp[i-1][j])a0

a1

…

ai-2

ai-1b0

b1

…

bj-2

bj-1dp[i-1][j]max95/87dp[0][0]=0 初始條件dp[i][0]=0 邊界情況dp[0][j]=0 邊界情況dp[i][j]=dp[i-1][j-1]+1 a[i-1]=b[j-1]dp[i][j]=max{dp[i][j-1]，dp[i-1][j]} a[i-1]≠b[j-1]狀態(tài)轉(zhuǎn)移方程在求出dp數(shù)組后，dp[m][n]就是a和b的最長公共子序列長度。96/871 defLCSlength(a,b): #求dp2 globaldp3 m,n=len(a),len(b)4 dp=[[0]*(n+1)foriinrange(m+1)]5 dp[0][0]=06 foriinrange(m+1): #將dp[i][0]置為07 dp[i][0]=08 forjinrange(0,n+1): #將dp[0][j]置為09 dp[0][j]=010 foriinrange(1,m+1):11 forjinrange(1,n+1): #循環(huán)處理a、b所有字符12 ifa[i-1]==b[j-1]:

#情況①13 dp[i][j]=dp[i-1][j-1]+114 else: #情況②15 dp[i][j]=max(dp[i][j-1],dp[i-1][j])16 returndp[m][n]【算法分析】算法的時間復雜度為O(mn)，空間復雜度為O(mn)。97/87

當求出dp后如何利用dp求一個最長公共子序列呢？分析狀態(tài)轉(zhuǎn)移方程最后兩行的計算過程可以看出：若dp[i][j]=dp[i-1][j-1]+1，有a[i-1]=b[j-1]，也就是說

a[i-1]/b[j-1]是LCS中的字符。若dp[i][j]=dp[i][j-1]，有a[i-1]≠b[j-1]，也就是說

a[i-1]/b[j-1]不是LCS中的字符。若dp[i][j]=dp[i-1][j]，有a[i-1]≠b[j-1]，同樣

a[i-1]/b[j-1]不是LCS中的字符。dp[i][j]=dp[i-1][j-1]+1 a[i-1]=b[j-1]dp[i][j]=max{dp[i][j-1]，dp[i-1][j]} a[i-1]≠b[j-1]dp

求一個LCS98/87

用一個字符串subs存放一個LCS，i=m，j=n開始向subs中添加k=dp[m][n]個字符，歸納為如下3種情況：若dp[i][j]=dp[i-1][j]（即當前dp元素值等于上方相鄰元素值），移到上一行即i減1，此時a[i]/b[j]不是LCS字符。若dp[i][j]=dp[i][j-1]（即當前dp元素值等于左邊相鄰元素值），移到左一列即j減1，此時a[i]/b[j]不是LCS字符。其他情況只能是dp[i][j]=dp[i-1][j-1]+1，移到左上方即i減1同時j減1，此時a[i]/b[j]是LCS的字符，將a[i]/b[j]添加到subs中。i,ji-1,ji-1,j-1i,j-1b[j]a[i]③②①99/87例如，a="abcbdb"，m=6，b="acbbabdbb"，n=9。

baacbbabdbb0123456789a00000000000b10111111111c20112222222b30122222222d40123333333b5012333344460123444455

若dp[i][j]=dp[i-1][j]，移到上一行，此時a[i]/b[j]不是LCS字符。

若dp[i][j]=dp[i][j-1]，移到左一列，此時a[i]/b[j]不是LCS字符。若dp[i][j]=dp[i-1][j-1]+1，移到左上方，a[i]/b[j]是LCS的字符。subs="acbdb"100/871 defgetasubs(a,b): #由dp構造subs2 subs="" #存放一個LCS3 m,n=len(a),len(b)4 k=dp[m][n] #k為a和b的最長公共子序列長度5 i,j=m,n6 whilek>0: #在subs中放入最長公共子序列(反向)7 ifdp[i][j]==dp[i-1][j]:8 i-=19 elifdp[i][j]==dp[i][j-1]:10 j-=111 else:12 subs+=a[i-1] #subs中添加a[i-1]13 i,j,k=i-1,j-1,k-114 ans=list(subs)15 ans.reverse()16 return"".join(ans) #返回逆置subs的字符串101/87設a和b是兩個字符串。現(xiàn)在要用最少的字符操作次數(shù)（最優(yōu)編輯距離），將字符串a(chǎn)編輯為字符串b。這里的字符編輯操作共有3種：刪除一個字符，插入一個字符或者將一個字符替換另一個字符。例如，a="sfdqxbw"，b="gfdgw"，結(jié)果為4。8.5.2編輯距離102