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

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ī)劃第8章保存子問題解—動態(tài)規(guī)劃1/878.5字符串動態(tài)規(guī)劃字符串動態(tài)規(guī)劃是指采用動態(tài)規(guī)劃算法求解字符串的相關問題。說明2/87一個字符串的子序列是指從該字符串中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。給定兩個字符串a(chǎn)和b，稱字符串c是a和b的公共子序列，是指c同是a和b的子序列。該問題是求兩個字符串a(chǎn)和b的最長公共子序列（LCS）。8.5.1最長公共子序列問題3/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]max4/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的最長公共子序列長度。5/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)。6/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

求一個LCS7/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]③②①8/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"9/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的字符串10/87設a和b是兩個字符串?，F(xiàn)在要用最少的字符操作次數(shù)（最優(yōu)編輯距離），將字符串a(chǎn)編輯為字符串b。這里的字符編輯操作共有3種：刪除一個字符，插入一個字符或者將一個字符替換另一個字符。例如，a="sfdqxbw"，b="gfdgw"，結果為4。8.5.2編輯距離11/87設計二維動態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]表示將a[0..i-1]（1≤i≤m）編輯為b[0..j-1]（1≤j≤n）的最優(yōu)編輯距離（即最少編輯操作次數(shù)）。當b為空串時，要刪除a中全部字符得到為b，即dp[i][0]=i（刪除a中i個字符，共i次操作）。當a為空串時，要在a中插入b的全部字符得到b，即dp[0][j]=j（向a中插入b的j個字符，共j次操作）。解a

b12/87

當兩個字符串a(chǎn)、b均不空時，若a[i-1]=b[j-1]時，這兩個字符不需要任何操作，即dp[i][j]=dp[i-1][j-1]。

當a[i-1]≠b[j-1]時，以下3種操作都可以達到目的：將a[i-1]替換為b[j-1]，有dp[i][j]=dp[i-1][j-1]+1（一次替換操作的次數(shù)計為1）。在a[i-1]字符后面插入b[j-1]字符，有dp[i][j]=dp[i][j-1]+1（一次插入操作的次數(shù)計為1）。刪除a[i-1]字符，有dp[i][j]=dp[i-1][j]+1（一次刪除操作的次數(shù)計為1）。此時dp[i][j]取上述三種操作的最小值。13/871 defeditdist(a,b): #求a到b的編輯距離2 m,n=len(a),len(b)3 dp=[[0]*(n+1)foriinrange(m+1)] #二維動態(tài)規(guī)劃數(shù)組4 foriinrange(1,m+1):5 dp[i][0]=i #把a的i個字符全部刪除轉(zhuǎn)換為b6 forjinrange(1,n+1):7 dp[0][j]=j #在a中插入b的全部字符轉(zhuǎn)換為b8 foriinrange(1,m+1):9 forjinrange(1,n+1):10 ifa[i-1]==b[j-1]:11 dp[i][j]=dp[i-1][j-1]12 else:13 dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1])+114 returndp[m][n]14/87時間復雜度為O(m×n)，空間復雜度為O(m×n)。算法分析15/878.6背包動態(tài)規(guī)劃背包動態(tài)規(guī)劃主要指采用動態(tài)規(guī)劃求解0/1背包問題、完全背包問題和多重背包問題及其類似的問題。說明16/87有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案。W=10物品編號重量w價值v026123265354446求解結果(最優(yōu)方案)

選取的物品:014

總價值=158.6.10/1背包問題17/87

設置二維動態(tài)規(guī)劃數(shù)組dp，dp[i][r]表示在物品0～i-1（共i個物品）中選擇物品并且背包容量為r（0≤r≤W）時最大價值，或者說只考慮前i個物品并且背包容量為r時最大價值。考慮物品i-1，分為兩種情況：若r<w[i-1]，說明物品i-1放不下，此時等效于只考慮前i-1個物品并且背包容量為r時的最大價值，所以有dp[i][r]=dp[i-1][r]。解18/87若r≥w[i-1]，說明物品i-1能夠放入背包。有兩種選擇：不選擇物品i-1即不將物品i-1放入背包，等同于情況①。選擇物品i-1即將物品i-1放入背包，這樣消耗了w[i-1]的背包容量，獲取了v[i-1]的價值，那么留給前i-1個物品的背包容量就只有r-w[i-1]了，此時的最大價值為dp[i-1][r-w[i-1]]+v[i-1]。

兩種選擇中取最大值。dp[i][r]=max{dp[i-1][r]，

dp[i-1][r-w[i-1]]+v[i-1]}0i-1，rdp[i-1][r]i-1，r-w[i-1]dp[i-1][r-w[i-1]]i，rv[i-1]19/87狀態(tài)轉(zhuǎn)移方程dp[i][0]=0（沒有裝入任何物品，總價值為0）

邊界情況dp[0][r]=0（沒有考慮任何物品，總價值為0）

邊界情況dp[i][r]=dp[i-1][r]

當r<w[i-1]時，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

否則在不放入和放入物品i-1之間取最大價值在求出dp數(shù)組后dp[n][W]元素就是答案。20/871 defknap(w,v,n,W): #動態(tài)規(guī)劃法求dp2 globaldp3 dp=[[0]*(W+1)foriinrange(n+1)] #二維動態(tài)規(guī)劃數(shù)組4 foriinrange(0,n):dp[i][0]=06 forrinrange(0,W+1):dp[0][r]=08 foriinrange(1,n+1):9 forrinrange(0,W+1):10 ifr<w[i-1]: 11 dp[i][r]=dp[i-1][r]12 else:13 dp[i][r]=max(dp[i-1][r],dp[i-1][r-w[i-1]]+v[i-1])14 returndp[n][W]【算法分析】時間復雜度和空間復雜度均為O(nW)。是多項式級？21/87

當求出dp數(shù)組后，如何推導出一個解向量x=（x0，x1，…，xn-1）呢？從前面狀態(tài)轉(zhuǎn)移方程的后兩行看出：若dp[i][r]=dp[i-1][r]，表示物品i-1放不下或者不放入物品i-1的情況，總之不選擇物品i-1。也就是說當前dp元素等于上方元素，不選擇對應的物品（物品i-1），并跳到上方位置。否則一定有dp[i][r]≠dp[i-1][r]成立，表示選擇物品i-1。也就是說當前dp元素不等于上方元素，選擇對應的物品，并跳到左上角dp[i-1][r-w[i-1]]的位置。dp[i][r]=dp[i-1][r]

當r<w[i-1]時，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

否則在不放入和放入物品i-1之間取最大價值dp

一個裝入方案22/87

ri012345678910w0=2000000000000w1=2100666666666w2=6200669999999w3=5300669999111114w4=4400669991011131450066991212151515若dp[i][r]=dp[i-1][r]，當前dp元素等于上方元素，不選擇物品i-1，并跳到上方位置，即dp[i][r]

dp[i-1][r]。否則當前dp元素等于上方元素，選擇對應的物品i-1，并跳到左上角dp[i-1][r-w[i-1]]的位置，即dp[i][r]

dp[i-1][r-w[i-1]]]。選擇物品4選擇物品1選擇物品023/871 defgetx(w): #回推求一個最優(yōu)方案2 globalx3 x=[0]*n4 i,r=n,W5 whilei>=1:6 ifdp[i][r]!=dp[i-1][r]:7 x[i-1]=1 #選取物品i-18 r=r-w[i-1]9 else:10 x[i-1]=0 #不選取物品i-111 i-=1dp[i][r]=dp[i-1][r]

當r<w[i-1]時，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

否則在不放入和放入物品i-1之間取最大價值24/87程序驗證n=5，w={2，2，6，5，4}，v={6，3，5，4，6}，W=10。25/87算法空間優(yōu)化dp[i][r]dp[r]r-w[i-1]dp[i-1]rdp[i]…r……dp[i-1][r]→dp[r]dp[i][r]→dp[r]dp[i-1][r-w[i-1]]→dp[r-w[i-1]]26/871 defknap1(w,v,n,W): #改進算法2 dp=[0]*(W+1) #一維動態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(W,-1,-1): #r按0到W的逆序（重點）5 ifr<w[i-1]:dp[r]=dp[r]6 else:dp[r]=max(dp[r],dp[r-w[i-1]]+v[i-1])7 returndp[W]27/871 defknap2(w,v,n,W): #改進算法2 dp=[0]*(W+1) #一維動態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(W,w[i-1]-1,-1): #按逆序（重點）5 dp[r]=max(dp[r],dp[r-w[i-1]]+v[i-1])6 returndp[W]上述算法可以等價地改為如下算法：28/87問題描述：給定一個含n個整數(shù)的數(shù)組nums（1≤n≤20，0≤nums[i]≤1000）和一個整數(shù)target（-1000≤target≤1000）。向數(shù)組中的每個整數(shù)前添加'+'或'-'，然后串聯(lián)起所有整數(shù)，可以構造一個表達式。

例如，nums={2，1}，可以在2之前添加'+'，在1之前添加'-'，然后串聯(lián)起來得到表達式

“+2-1”。

設計一個算法求可以通過上述方法構造的運算結果等于target的不同表達式的數(shù)目。

要求設計如下方法：

def

findTargetSumWays(self,

nums,target)

->

int:8.6.2實戰(zhàn)—目標和（LeetCode494★）29/87不妨用w表示nums數(shù)組，先求出w中所有整數(shù)和s，顯然s<target時即使全部加上'+'也不可能成立，此時返回0（無解）。否則本問題就是求以下等式成立的不同表達式的數(shù)目（±表示取'+'或者'-'之一）：解用s減去兩邊后轉(zhuǎn)換為：等同于：30/87對于

部分，如果取'-'（對應原來的'+'）則為0，如果取'+'（對應原來的'-'）則為2w[i]。考慮只取'-'的部分（其他取'+'），假設對應的下標為i1，i2，…，ik，則為：其中i1，i2，…，ik，是0，1，…，n-1的一個子序列，這樣該問題等價于在w數(shù)組中選擇添加'-'的元素和等于(s-target)/2的組合總數(shù)，屬于典型的0/1背包問題。31/87

采用動態(tài)規(guī)劃求解，設置二維動態(tài)規(guī)劃數(shù)組dp，dp[i][r]表示在nums[0～i-1]（共i個整數(shù)）中選擇若干整數(shù)添加'-'（其他添加'+'）并且和恰好為r的組合總數(shù)，對應的狀態(tài)轉(zhuǎn)移方程如下：dp[0][0]=1dp[i][r]=dp[i-1][r] r<nums[i-1]dp[i][r]=dp[i-1][r-nums[i-1]]+dp[i-1][r] 否則(選擇和不選擇nums[i-1]的組合數(shù)之和)32/871 class

Solution:2

def

findTargetSumWays(self,nums,target)

->

int:3

n,s=len(nums),sum(nums)4

if

target>s:return

05

if

(s-target)%2==1:return

0選擇添加'-'的元素和為(s-target)/233/876

W=(s-target)//27

dp=[[0]*(W+1)

for

i

in

range(n+1)]8

dp[0][0]=19

for

i

in

range(1,n+1):10

for

r

in

range(0,W+1):11

if

r<nums[i-1]:12

dp[i][r]=dp[i-1][r]13

else:14

dp[i][r]=dp[i-1][r-nums[i-1]]+dp[i-1][r]15

return

dp[n][W]上述程序提交時通過，執(zhí)行用時為100ms，內(nèi)存消耗為15.1MB。34/87采用類似0/1背包問題的改進算法，設置一個一維動態(tài)規(guī)劃設置dp，dp[r]表示選擇整數(shù)和為r的組合總數(shù)?？臻g優(yōu)化35/871 class

Solution:2

def

findTargetSumWays(self,

nums,target)

->

int:3

n,s=len(nums),sum(nums)4

if

target>s:return

05

if

(s-target)%2==1:return

06

W=(s-target)//27

dp=[0]*(W+1)8

dp[0]=19

for

i

in

range(1,n+1):10

for

r

in

range(W,nums[i-1]-1,-1): #r逆序11

dp[r]+=dp[r-nums[i-1]]

#組合總數(shù)是累計關系12

return

dp[W]上述程序提交時通過，執(zhí)行用時為64ms，內(nèi)存消耗為14.9MB。36/87有n種重量和價值分別為wi、vi（0≤i<n）的物品，從這些物品中挑選總重量不超過W的物品，每種物品可以挑選任意多件。求挑選物品的最大價值。8.6.3完全背包問題37/87設置動態(tài)規(guī)劃二維數(shù)組dp，dp[i][r]表示從物品0～i-1（共i種物品）中選出重量不超過r的物品的最大總價值。顯然有dp[i][0]=0（背包不能裝入任何物品時，總價值為0），dp[0][j]=0（沒有任何物品可裝入時，總價值為0），將它們作為邊界情況，為此一次性將dp數(shù)組初始化為0。一般情況：解dp[i][r]=maxk×w[i-1]≤r{dp[i-1]

[r-k*w[i-1]]+k*v[i-1]}0i-1,rdp[i-1][r]i-1,r-w[i-1]dp[i-1][r-w[i-1]]i，rv[i-1]i-1,r-k×w[i-1]dp[i-1][r-k×w[i-1]]k×v[i-1]┇38/87另外設置二維數(shù)組fk，其中fk[i][r]存放dp[i][r]得到最大值時物品i-1挑選的件數(shù)?？紤]物品i-1，可以選擇0到k（k×w[i-1]≤r）次。39/87狀態(tài)轉(zhuǎn)移方程dp[i][r]=maxk×w[i-1]≤r{dp[i-1][r-k×w[i-1]]+k×v[i-1]}fk[i][r]=k; 物品i-1取k件

ji0123456700[0]0[0]0[0]0[0]0[0]0[0]0[0]0[0]10[0]0[0]0[0]4[1]4[1]4[1]8[2]8[2]20[0]0[0]0[0]4[0]5[1]5[1]8[0]9[1]30[0]0[0]3[1]4[0]6[2]7[1]9[3]10[2]n=3，W=7，w=（3，4，2），v=（4，5，3）最優(yōu)方案：物品2挑選2件，物品1挑選0件，物品0挑選1件。40/871 defcompleteknap(w,v,n,W): #采用動態(tài)規(guī)劃方法求dp和fk2 globaldp,fk3 dp=[[0]*(W+1)foriinrange(n+1)]4 fk=[[0]*(W+1)foriinrange(n+1)]5 foriinrange(1,n+1):6 forrinrange(0,W+1):7 k=08 whilek*w[i-1]<=r:9 ifdp[i][r]<dp[i-1][r-k*w[i-1]]+k*v[i-1]:10 dp[i][r]=dp[i-1][r-k*w[i-1]]+k*v[i-1]

#物品i-1取k件11 fk[i][r]=k12 k+=113 returndp[n][W]41/871 defgetx(): #回推求一個最優(yōu)選擇方案2 i,r=n,W3 whilei>=1:4 print("選擇物品%d共%d件"%(i-1,fk[i][r]))5 r-=fk[i][r]*w[i-1] #剩余重量6 i-=1【算法分析】completeKnap算法中包含三重循環(huán)，k的循環(huán)最壞可能從0到W，所以算法的時間復雜度為O(nW2)。42/87算法時間優(yōu)化將完全背包問題轉(zhuǎn)換為這樣的0/1背包問題，物品i出現(xiàn)

W/w[i]

次。例如對于完全背包問題n=3，W=7，w=（3，4，2），v=（4，5，3），物品0最多取W/3=2次，物品1最多取W/4=1次，物品2最多取W/2=3次，對應的0/1背包問題是W=7，n=6，w=（3，3，4，2，2，2），v=（4，4，5，3，3，3）。后者的最大價值與前者是相同的。43/871 defcompleteknap1(w,v,n,W): #時間改進算法2 dp=[[0]*(W+1)foriinrange(n+1)]3 foriinrange(1,n+1):4 forrinrange(0,W+1):5 ifr<w[i-1]: #物品i-1放不下6 dp[i][r]=dp[i-1][r]7 else: #在不選擇和選擇物品i-1（多次）中求最大值8 dp[i][r]=max(dp[i-1][r],dp[i][r-w[i-1]]+v[i-1])9returndp[n][W] #返回總價值【算法分析】上述算法中包含兩重循環(huán)，所以算法的時間復雜度為O(nW)。44/87算法空間優(yōu)化1 defcompleteknap2(w,v,n,W): #空間改進算法2 dp=[0]*(W+1) #一維動態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(w[i-1],W+1): #r按順序5 dp[r]=max(dp[r],dp[r-w[i-1]]+v[i-1])6 returndp[W]1 defknap2(w,v,n,W): #改進算法2 dp=[0]*(W+1) #一維動態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(W,w[i-1]-1,-1): #按逆序（重點）5 dp[r]=max(dp[r],dp[r-w[i-1]]+v[i-1])6 returndp[W]45/87問題描述：給定一個含n個整數(shù)的數(shù)組coins，表示不同面額的硬幣，以及一個表示總金額的整數(shù)amount。設計一個算法求可以湊成總金額所需的最少的硬幣個數(shù)，如果沒有任何一種硬幣組合能組成總金額則返回-1

。可以認為每種硬幣的數(shù)量是無限的。

例如，coins={1，2，5}，amount=11，對應的硬幣組合是1，5，5，答案為3。

要求設計如下方法：

def

coinChange(self,coins,amount)

->

int:8.6.4實戰(zhàn)—零錢兌換（LeetCode332）46/87由于每種硬幣的數(shù)量是無限的，該問題轉(zhuǎn)換為完全背包問題，只是這里求最少的硬幣個數(shù)，相當于每個硬幣的價值為1，并且將max改為min。采用改進的完全背包動態(tài)規(guī)劃算法，設置一維動態(tài)規(guī)劃設置dp，dp[r]表示總金額為r的最少的硬幣個數(shù)。另外考慮特殊情況，將dp所有元素初始化為∞，當最后出現(xiàn)dp[amount]為∞，說明沒有任何一種硬幣組合能組成amount金額，返回-1。解47/871 class

Solution:2

def

coinChange(self,coins,amount)

->

int:3

INF=0x3f3f3f3f

#表示∞4

if

amount==0:return

05

n=len(coins)6

if

n==1

and

amount%coins[0]!=0:return

-17

dp=[INF]*(amount+1)

#一維動態(tài)規(guī)劃數(shù)組,初始化為∞8

dp[0]=09

for

i

in

range(1,n+1):10

for

r

in

range(coins[i-1],amount+1):11

dp[r]=min(dp[r],dp[r-coins[i-1]]+1)12

return

-1

if

dp[amount]==INF

else

dp[amount]48/87上述程序提交時通過，執(zhí)行用時執(zhí)行用時12ms，內(nèi)存消耗37.5MB。49/878.6.5多重背包問題*有n種重量和價值分別為wi、vi（0≤i<n）的物品，物品i有si件。從這些物品中挑選總重量不超過W的物品，每種物品可以挑選多件，求挑選物品的最大價值。例如，n=3，W=7，w={3，4，2}，v={4，5，3}，s={2，2，1}，對應的最大價值為9，一個最優(yōu)方案是選擇物品0和1各一件。50/87設置動態(tài)規(guī)劃二維數(shù)組dp，dp[i][r]表示從物品0～i-1（共i個物品）中選出重量不超過r的物品的最大總價值，選擇物品i的最多件數(shù)為s[i]。解51/871 defmultiknap(w,v,n,W): #求解多重背包問題2 globaldp3 dp=[[0]*(W+1)foriinrange(n+1)]

#二維動態(tài)規(guī)劃數(shù)組4 foriinrange(1,n+1):5 forrinrange(0,W+1):6 k=07 whilek<=s[i-1]:8 ifk*w[i-1]<=r: #不超重時9 dp[i][r]=max(dp[i][r],dp[i-1][r-k*w[i-1]]+k*v[i-1])10 k+=111 returndp[n][W]52/878.7樹形動態(tài)規(guī)劃樹形動態(tài)規(guī)劃指基于樹結構（含二叉樹）的動態(tài)規(guī)劃算法設計。由于樹具有嚴格的分層，使得動態(tài)規(guī)劃的階段十分清晰，例如父子結點的關系可能就是兩個階段之間的聯(lián)系。樹形動態(tài)規(guī)劃涉及樹的搜索，通常采用深度優(yōu)先搜索。說明53/87【例8-2】某學校要開一個慶祝晚會，學校共有n個員工，員工編號為1～n，員工之間有上下級關系，這樣構成一棵關系樹結構。為了讓員工開心，晚會組織者決定不會同時邀請一個員工和他的直屬上級。每個員工參加晚會有一個開心指數(shù)，用整型數(shù)組value表示，value[i]表示員工i的開心指數(shù)。問題是求參加晚會的所有員工開心指數(shù)和的最大值，給出采用動態(tài)規(guī)劃求解的思路。54/87采用樹形動態(tài)規(guī)劃方法求解，樹中每個結點表示一個員工，每個員工有兩種狀態(tài)，即參加和不參加慶祝晚會。為此設計二維動態(tài)規(guī)劃數(shù)組dp來描述狀態(tài)（初始時所有元素設置為0），其中dp[i][1]表示員工i參加慶祝晚會時對應子樹的最大開心指數(shù)和，dp[i][0]表示員工i不參加慶祝晚會時對應子樹的最大開心指數(shù)和。解55/87（1）員工i有下級員工，員工i有參加和不參加晚會兩種可能。

①員工i參加晚會，那么他的所有下級員工都不能參加，則結點i子樹的最大開心指數(shù)和為dp[i][1]，如圖(a)所示，即：dp[i][1]=value[i]+

son為員工i的下級員工dp[son][0]對于員工i的各種情況分析如下：(a)員工i參加晚會dp[i][1]ij1jkdp[j1][0]dp[jk][1]…56/87②員工i不參加慶祝晚會，那么他的每個下級員工可以參加也可以不參加，則結點i子樹的最大開心指數(shù)和為dp[i][0]，即取員工i的所有下級員工參加和不參加的最大開心指數(shù)和的最大值，然后累計起來，如圖(b)所示，即：dp[i][0]=

son為員工i的下級員工max{dp[son][1]，dp[son][0]}(b)員工i不參加晚會dp[i][0]ij1jkmax{dp[j1][1]，dp[j1][0]}…max{dp[jk][1]，dp[jk][0]}57/87（2）員工i沒有下級員工，員工i有參加和不參加晚會兩種可能。

①員工i參加慶祝晚會，結點i子樹的最大開心指數(shù)和為dp[i][1]，有：

dp[i][1]=value[i]

②員工i不參加慶祝晚會，則結點i子樹的最大開心指數(shù)和為dp[i][0]，有：dp[i][0]=0在求出dp數(shù)組后，對于根結點root，則max(dp[root][0]，dp[root][1])就是最后的答案。對于員工i的各種情況分析如下：58/87問題描述：有一個礦洞由多個礦區(qū)組成，每個礦區(qū)有若干煤炭，礦洞只有一個入口，稱之為根。除了根之外，每個礦區(qū)有且只有一個父礦區(qū)與之相連。所有礦區(qū)的排列類似于一棵二叉樹。

A進入礦洞想找到盡可能多的煤炭，由于某種原因A不能在同一天晚上拿走兩個直接相連礦區(qū)的煤炭。求A一晚能夠拿走的最多煤炭。

例如，一個礦洞結構如下圖所示，二叉樹結點中的數(shù)字表示煤炭數(shù)量，A一晚能夠拿走的最多煤炭=3+3+1=7。323138.7.2實戰(zhàn)—找礦（LeetCode337★★）59/87

采用遞歸分治的思路，設f(root)表示在root為根的二叉樹中的最大收益（能夠拿走的最多煤炭），則有兩種操作：

（1）拿root結點（即拿走root結點中的煤炭），依題意則不能拿root的孩子結點（root結點與其孩子結點直接相連），但可以拿root孩子結點的孩子，如圖(a)所示，該情況對應的最大收益用money1表示，則：money1=root.val+f(root.left.left)+f(root.left.right)+ f(root.right.left)+f(root.right.right)解法1—備忘錄方法root(a)情況①60/87

（2）不拿root結點，則可以拿root.left和root.right結點，如圖(b)所示，該情況對應的最大收益用money2表示，則：money2=f(root.left)+f(root.right)。最后返回max(money1，money2)即可。root(b)情況②61/871 class

Solution:2

def

rob(self,

root:

Optional[TreeNode])

->

int:3

if

root==None:return

04

return

self.dfs(root)56

def

dfs(self,root):

#遞歸算法7

if

root==None:return

08

money1=root.val9

if

root.left:10

money1+=self.dfs(root.left.left)+ self.dfs(root.left.right)11

if

root.right:12

money1+=self.dfs(root.right.left)+ self.dfs(root.right.right)13

money2=self.dfs(root.left)+self.dfs(root.right)14

return

max(money1,money2)超時，存在大量重復的子問題計算，采用備忘錄方法。62/871 class

Solution:2

hmap={}

#定義哈希表作為動態(tài)規(guī)劃數(shù)組3

def

rob(self,

root:

Optional[TreeNode])

->

int:4

if

root==None:return

05

return

self.dfs(root)采用備忘錄方法，用哈希映射將字典對象hmap存儲已經(jīng)求出的子問題解，以消除重復計算，也就是說若結點root在hmap中找到了答案就直接返回。63/877 def

dfs(self,root):

#遞歸算法8

if

root==None:return

09

if

root

in

self.hmap:return

self.hmap[root]10

money1=root.val11

if

root.left:12

money1+=self.dfs(root.left.left)+ self.dfs(root.left.right)13

if

root.right:14

money1+=self.dfs(root.right.left)+ self.dfs(root.right.right)15

money2=self.dfs(root.left)+self.dfs(root.right)16

self.hmap[root]=max(money1,money2)

#將子問題的解存放到hmap中17 return

self.hmap[root]64/87對于當前結點root，有拿和不拿兩種可能。設計一維動態(tài)規(guī)劃數(shù)組dp[2]，其中dp[0]表示不拿結點root的最大收益，dp[1]表示拿結點root的最大收益，其左右子樹的動態(tài)規(guī)劃數(shù)組分別用ldp[]和rdp[]表示。解法2—動態(tài)規(guī)劃65/87

（1）不拿結點root，則root的左右孩子結點可以選擇拿或不拿，以root為根結點的樹的最大收益=左子樹的最大收益+右子樹的最大收益，其中左子樹的最大收益=max(拿左孩子結點，不拿左孩子結點)，右子樹的最大收益=max(拿右孩子結點，不拿右孩子結點)。這樣有

dp[0]=max(ldp[0]，ldp[1])+max(rdp[0]，rdp[1])。root66/87

（2）拿結點root，則以root為根結點的樹的最大收益=root.val+不拿左子結點時左子樹的最大收益+不拿右子結點時右子樹的最大收益，即

dp[1]=root.val+ldp[0]+rdp[0]。最后返回max(dp[0]，dp[1])即可。root67/871 class

Solution:2

def

rob(self,

root:

Optional[TreeNode])

->

int:3

if

root==None:return

04

dp=self.dfs(root)5

return

max(dp[0],dp[1])67

def

dfs(self,root):

#動態(tài)規(guī)劃算法8

dp=[0,0]9

if

root==None:return

dp10

ldp=self.dfs(root.left)11

rdp=self.dfs(root.right)12

dp[0]=max(ldp[0],ldp[1])+max(rdp[0],rdp[1])13

dp[1]=root.val+ldp[0]+rdp[0]14

return

dp68/878.7.3實戰(zhàn)—監(jiān)控二叉樹（LeetCode968★★★）自學(老師講的太多了)69/878.8區(qū)間動態(tài)規(guī)劃區(qū)間動態(tài)規(guī)劃通常以連續(xù)區(qū)間的求解作為子問題，例如區(qū)間[i,j]上的最優(yōu)解用dp[i][j]表示。先在小區(qū)間上進行動態(tài)規(guī)劃得到子問題的最優(yōu)解，然后再利用小區(qū)間的最優(yōu)解合并產(chǎn)生大區(qū)間的最優(yōu)解。區(qū)間動態(tài)規(guī)劃一般需要從小到大枚舉所有可能的區(qū)間，在枚舉時不能夠像平常的從頭到尾遍歷，而是以區(qū)間的長度len為循環(huán)變量，在不同的長度區(qū)間里枚舉所有可能的狀態(tài)，并從中選取最優(yōu)解。合并操作一般是把左、右兩個相鄰的子區(qū)間合并。說明70/87【例8-3】給定一個字符串s，每一次操作可以在s的任意位置插入任意字符。求讓s成為回文串的最少操作次數(shù)，給出對應的狀態(tài)轉(zhuǎn)移方程。71/87

設置二維動態(tài)規(guī)劃設置dp，dp[i][j]表示將子串s[i..j]（含s[i]和s[j]字符）變成回文串的最少操作次數(shù)（每次操作添加一個字符）。

（1）如果s[i]=s[j]，那么最外層已經(jīng)形成了回文，接下來只需要繼續(xù)考慮s[i+1..j-1]，即dp[i][j]=dp[i+1][j-1]。

解72/87（2）如果s[i]≠s[j]，可以采用以下兩種操作使其變?yōu)榛匚模涸趕[j]后面添加一個字符s[i]（計一次操作），接下來只需要繼續(xù)考慮s[i+1..j]，對應的操作次數(shù)=dp[i+1][j]+1。在s[i]前面添加一個字符s[j]（計一次操作），接下來只需要繼續(xù)考慮s[i..j-1]，對應的操作次數(shù)=dp[i][j-1]+1。

兩種操作中取最小操作次數(shù)，即

dp[i][j]=min{dp[i+1][j]+1,dp[i][j-1]+1}。73/87dp[i][j]=0 當j<i+1時dp[i][j]=dp[i+1][j-1] 當s[i]=s[j]dp[i][j]=min{dp[i+1][j]+1,dp[i][j-1]+1} 當s[i]≠s[j]對應的狀態(tài)轉(zhuǎn)移方程如下：74/87問題描述：假設A是p×q矩陣，B是q×r矩陣，在計算C=A×B的標準算法中需要做pqr次數(shù)乘。給定n（n>2）個矩陣A1、A2、…、An，其中Ai和Ai+1（1≤i≤n-1）是可乘的，求這n個矩陣的乘積A1×A2×…×An時最少的數(shù)乘次數(shù)是多少？8.8.2矩陣連乘問題75/87用一維數(shù)組p[0..n]表示n個矩陣的大小，p[0]表示A1的行數(shù)，p[i]表示Ai（1≤i≤n）的列數(shù)。例如，n=3，A1、A2和A3的大小分別為10×100、100×50和50×5。對應的p[0..3]={10，100，50，5}。解76/87Ap×q×Bq×r的結果是矩陣Ap×r，需要做pqr次數(shù)乘。用A[i..j]表示Ai×…×Aj的連乘結果，其中Ai為p[i-1]×p[i]大小的矩陣，…，Aj為p[j-1]×p[j]大小的矩陣。則A[i..j]是一個p[i-1]×p[j]大小的矩陣。77/87采用區(qū)間動態(tài)規(guī)劃方法求解。設計二維動