《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件 第8章動(dòng)態(tài)規(guī)劃2

8.1動(dòng)態(tài)規(guī)劃概述8.2一維動(dòng)態(tài)規(guī)劃CONTENTS提綱8.3二維動(dòng)態(tài)規(guī)劃8.4三維動(dòng)態(tài)規(guī)劃8.5字符串動(dòng)態(tài)規(guī)劃8.6背包動(dòng)態(tài)規(guī)劃8.7樹(shù)形動(dòng)態(tài)規(guī)劃8.8區(qū)間動(dòng)態(tài)規(guī)劃第8章保存子問(wèn)題解—?jiǎng)討B(tài)規(guī)劃1/878.5字符串動(dòng)態(tài)規(guī)劃字符串動(dòng)態(tài)規(guī)劃是指采用動(dòng)態(tài)規(guī)劃算法求解字符串的相關(guān)問(wèn)題。說(shuō)明2/87一個(gè)字符串的子序列是指從該字符串中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。給定兩個(gè)字符串a(chǎn)和b，稱字符串c是a和b的公共子序列，是指c同是a和b的子序列。該問(wèn)題是求兩個(gè)字符串a(chǎn)和b的最長(zhǎng)公共子序列（LCS）。8.5.1最長(zhǎng)公共子序列問(wèn)題3/87設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]為（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長(zhǎng)公共子序列長(zhǎng)度，求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的最長(zhǎng)公共子序列長(zhǎng)度。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]【算法分析】算法的時(shí)間復(fù)雜度為O(mn)，空間復(fù)雜度為O(mn)。6/87

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

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

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

求一個(gè)LCS7/87

用一個(gè)字符串subs存放一個(gè)LCS，i=m，j=n開(kāi)始向subs中添加k=dp[m][n]個(gè)字符，歸納為如下3種情況：若dp[i][j]=dp[i-1][j]（即當(dāng)前dp元素值等于上方相鄰元素值），移到上一行即i減1，此時(shí)a[i]/b[j]不是LCS字符。若dp[i][j]=dp[i][j-1]（即當(dāng)前dp元素值等于左邊相鄰元素值），移到左一列即j減1，此時(shí)a[i]/b[j]不是LCS字符。其他情況只能是dp[i][j]=dp[i-1][j-1]+1，移到左上方即i減1同時(shí)j減1，此時(shí)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]，移到上一行，此時(shí)a[i]/b[j]不是LCS字符。

若dp[i][j]=dp[i][j-1]，移到左一列，此時(shí)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構(gòu)造subs2 subs="" #存放一個(gè)LCS3 m,n=len(a),len(b)4 k=dp[m][n] #k為a和b的最長(zhǎng)公共子序列長(zhǎng)度5 i,j=m,n6 whilek>0: #在subs中放入最長(zhǎng)公共子序列(反向)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設(shè)a和b是兩個(gè)字符串?，F(xiàn)在要用最少的字符操作次數(shù)（最優(yōu)編輯距離），將字符串a(chǎn)編輯為字符串b。這里的字符編輯操作共有3種：刪除一個(gè)字符，插入一個(gè)字符或者將一個(gè)字符替換另一個(gè)字符。例如，a="sfdqxbw"，b="gfdgw"，結(jié)果為4。8.5.2編輯距離11/87設(shè)計(jì)二維動(dòng)態(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ù)）。當(dāng)b為空串時(shí)，要?jiǎng)h除a中全部字符得到為b，即dp[i][0]=i（刪除a中i個(gè)字符，共i次操作）。當(dāng)a為空串時(shí)，要在a中插入b的全部字符得到b，即dp[0][j]=j（向a中插入b的j個(gè)字符，共j次操作）。解a

b12/87

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

當(dāng)a[i-1]≠b[j-1]時(shí)，以下3種操作都可以達(dá)到目的：將a[i-1]替換為b[j-1]，有dp[i][j]=dp[i-1][j-1]+1（一次替換操作的次數(shù)計(jì)為1）。在a[i-1]字符后面插入b[j-1]字符，有dp[i][j]=dp[i][j-1]+1（一次插入操作的次數(shù)計(jì)為1）。刪除a[i-1]字符，有dp[i][j]=dp[i-1][j]+1（一次刪除操作的次數(shù)計(jì)為1）。此時(shí)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)] #二維動(dòng)態(tài)規(guī)劃數(shù)組4 foriinrange(1,m+1):5 dp[i][0]=i #把a(bǔ)的i個(gè)字符全部刪除轉(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時(shí)間復(fù)雜度為O(m×n)，空間復(fù)雜度為O(m×n)。算法分析15/878.6背包動(dòng)態(tài)規(guī)劃背包動(dòng)態(tài)規(guī)劃主要指采用動(dòng)態(tài)規(guī)劃求解0/1背包問(wèn)題、完全背包問(wèn)題和多重背包問(wèn)題及其類(lèi)似的問(wèn)題。說(shuō)明16/87有n個(gè)編號(hào)為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價(jià)值為v={v0，v1，…，vn-1}，給定一個(gè)容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個(gè)物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價(jià)值最大的方案。W=10物品編號(hào)重量w價(jià)值v026123265354446求解結(jié)果(最優(yōu)方案)

選取的物品:014

總價(jià)值=158.6.10/1背包問(wèn)題17/87

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

邊界情況dp[0][r]=0（沒(méi)有考慮任何物品，總價(jià)值為0）

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

當(dāng)r<w[i-1]時(shí)，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

否則在不放入和放入物品i-1之間取最大價(jià)值在求出dp數(shù)組后dp[n][W]元素就是答案。20/871 defknap(w,v,n,W): #動(dòng)態(tài)規(guī)劃法求dp2 globaldp3 dp=[[0]*(W+1)foriinrange(n+1)] #二維動(dòng)態(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]【算法分析】時(shí)間復(fù)雜度和空間復(fù)雜度均為O(nW)。是多項(xiàng)式級(jí)？21/87

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

當(dāng)r<w[i-1]時(shí)，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

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

一個(gè)裝入方案22/87

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

dp[i-1][r]。否則當(dāng)前dp元素等于上方元素，選擇對(duì)應(yīng)的物品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): #回推求一個(gè)最優(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]

當(dāng)r<w[i-1]時(shí)，物品i-1放不下dp[i][r]=max{dp[i-1][r]，dp[i-1][r-w[i-1]]+v[i-1]}

否則在不放入和放入物品i-1之間取最大價(jià)值24/87程序驗(yàn)證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): #改進(jìn)算法2 dp=[0]*(W+1) #一維動(dòng)態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(W,-1,-1): #r按0到W的逆序（重點(diǎn)）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): #改進(jìn)算法2 dp=[0]*(W+1) #一維動(dòng)態(tài)規(guī)劃數(shù)組3 foriinrange(1,n+1):4 forrinrange(W,w[i-1]-1,-1): #按逆序（重點(diǎn)）5 dp[r]=max(dp[r],dp[r-w[i-1]]+v[i-1])6 returndp[W]上述算法可以等價(jià)地改為如下算法：28/87問(wèn)題描述：給定一個(gè)含n個(gè)整數(shù)的數(shù)組nums（1≤n≤20，0≤nums[i]≤1000）和一個(gè)整數(shù)target（-1000≤target≤1000）。向數(shù)組中的每個(gè)整數(shù)前添加'+'或'-'，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè)表達(dá)式。

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

“+2-1”。

設(shè)計(jì)一個(gè)算法求可以通過(guò)上述方法構(gòu)造的運(yùn)算結(jié)果等于target的不同表達(dá)式的數(shù)目。

要求設(shè)計(jì)如下方法：

def

findTargetSumWays(self,

nums,target)

->

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

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

采用動(dòng)態(tài)規(guī)劃求解，設(shè)置二維動(dòng)態(tài)規(guī)劃數(shù)組dp，dp[i][r]表示在nums[0～i-1]（共i個(gè)整數(shù)）中選擇若干整數(shù)添加'-'（其他添加'+'）并且和恰好為r的組合總數(shù)，對(duì)應(yīng)的狀態(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]上述程序提交時(shí)通過(guò)，執(zhí)行用時(shí)為100ms，內(nèi)存消耗為15.1MB。34/87采用類(lèi)似0/1背包問(wèn)題的改進(jìn)算法，設(shè)置一個(gè)一維動(dòng)態(tài)規(guī)劃設(shè)置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ù)是累計(jì)關(guān)系12

return

dp[W]上述程序提交時(shí)通過(guò)，執(zhí)行用時(shí)為64ms，內(nèi)存消耗為14.9MB。36/87有n種重量和價(jià)值分別為wi、vi（0≤i<n）的物品，從這些物品中挑選總重量不超過(guò)W的物品，每種物品可以挑選任意多件。求挑選物品的最大價(jià)值。8.6.3完全背包問(wèn)題37/87設(shè)置動(dòng)態(tài)規(guī)劃二維數(shù)組dp，dp[i][r]表示從物品0～i-1（共i種物品）中選出重量不超過(guò)r的物品的最大總價(jià)值。顯然有dp[i][0]=0（背包不能裝入任何物品時(shí)，總價(jià)值為0），dp[0][j]=0（沒(méi)有任何物品可裝入時(shí)，總價(jià)值為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è)置二維數(shù)組fk，其中fk[i][r]存放dp[i][r]得到最大值時(shí)物品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): #采用動(dòng)態(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(): #回推求一個(gè)最優(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，所以算法的時(shí)間復(fù)雜度為O(nW2)。42/87算法時(shí)間優(yōu)化將完全背包問(wèn)題轉(zhuǎn)換為這樣的0/1背包問(wèn)題，物品i出現(xiàn)

W/w[i]

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

。可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

例如，coins={1，2，5}，amount=11，對(duì)應(yīng)的硬幣組合是1，5，5，答案為3。

要求設(shè)計(jì)如下方法：

def

coinChange(self,coins,amount)

->

int:8.6.4實(shí)戰(zhàn)—零錢(qián)兌換（LeetCode332）46/87由于每種硬幣的數(shù)量是無(wú)限的，該問(wèn)題轉(zhuǎn)換為完全背包問(wèn)題，只是這里求最少的硬幣個(gè)數(shù)，相當(dāng)于每個(gè)硬幣的價(jià)值為1，并且將max改為min。采用改進(jìn)的完全背包動(dòng)態(tài)規(guī)劃算法，設(shè)置一維動(dòng)態(tài)規(guī)劃設(shè)置dp，dp[r]表示總金額為r的最少的硬幣個(gè)數(shù)。另外考慮特殊情況，將dp所有元素初始化為∞，當(dāng)最后出現(xiàn)dp[amount]為∞，說(shuō)明沒(méi)有任何一種硬幣組合能組成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)

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

#二維動(dòng)態(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: #不超重時(shí)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樹(shù)形動(dòng)態(tài)規(guī)劃樹(shù)形動(dòng)態(tài)規(guī)劃指基于樹(shù)結(jié)構(gòu)（含二叉樹(shù)）的動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)。由于樹(shù)具有嚴(yán)格的分層，使得動(dòng)態(tài)規(guī)劃的階段十分清晰，例如父子結(jié)點(diǎn)的關(guān)系可能就是兩個(gè)階段之間的聯(lián)系。樹(shù)形動(dòng)態(tài)規(guī)劃涉及樹(shù)的搜索，通常采用深度優(yōu)先搜索。說(shuō)明53/87【例8-2】某學(xué)校要開(kāi)一個(gè)慶祝晚會(huì)，學(xué)校共有n個(gè)員工，員工編號(hào)為1～n，員工之間有上下級(jí)關(guān)系，這樣構(gòu)成一棵關(guān)系樹(shù)結(jié)構(gòu)。為了讓員工開(kāi)心，晚會(huì)組織者決定不會(huì)同時(shí)邀請(qǐng)一個(gè)員工和他的直屬上級(jí)。每個(gè)員工參加晚會(huì)有一個(gè)開(kāi)心指數(shù)，用整型數(shù)組value表示，value[i]表示員工i的開(kāi)心指數(shù)。問(wèn)題是求參加晚會(huì)的所有員工開(kāi)心指數(shù)和的最大值，給出采用動(dòng)態(tài)規(guī)劃求解的思路。54/87采用樹(shù)形動(dòng)態(tài)規(guī)劃方法求解，樹(shù)中每個(gè)結(jié)點(diǎn)表示一個(gè)員工，每個(gè)員工有兩種狀態(tài)，即參加和不參加慶祝晚會(huì)。為此設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp來(lái)描述狀態(tài)（初始時(shí)所有元素設(shè)置為0），其中dp[i][1]表示員工i參加慶祝晚會(huì)時(shí)對(duì)應(yīng)子樹(shù)的最大開(kāi)心指數(shù)和，dp[i][0]表示員工i不參加慶祝晚會(huì)時(shí)對(duì)應(yīng)子樹(shù)的最大開(kāi)心指數(shù)和。解55/87（1）員工i有下級(jí)員工，員工i有參加和不參加晚會(huì)兩種可能。

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

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

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

①員工i參加慶祝晚會(huì)，結(jié)點(diǎn)i子樹(shù)的最大開(kāi)心指數(shù)和為dp[i][1]，有：

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

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

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

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

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

（1）拿root結(jié)點(diǎn)（即拿走root結(jié)點(diǎn)中的煤炭），依題意則不能拿root的孩子結(jié)點(diǎn)（root結(jié)點(diǎn)與其孩子結(jié)點(diǎn)直接相連），但可以拿root孩子結(jié)點(diǎn)的孩子，如圖(a)所示，該情況對(duì)應(yīng)的最大收益用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結(jié)點(diǎn)，則可以拿root.left和root.right結(jié)點(diǎn)，如圖(b)所示，該情況對(duì)應(yīng)的最大收益用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)超時(shí)，存在大量重復(fù)的子問(wèn)題計(jì)算，采用備忘錄方法。62/871 class

Solution:2

hmap={}

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

def

rob(self,

root:

Optional[TreeNode])

->

int:4

if

root==None:return

05

return

self.dfs(root)采用備忘錄方法，用哈希映射將字典對(duì)象hmap存儲(chǔ)已經(jīng)求出的子問(wèn)題解，以消除重復(fù)計(jì)算，也就是說(shuō)若結(jié)點(diǎn)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)

#將子問(wèn)題的解存放到hmap中17 return

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

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

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

（2）拿結(jié)點(diǎn)root，則以root為根結(jié)點(diǎn)的樹(shù)的最大收益=root.val+不拿左子結(jié)點(diǎn)時(shí)左子樹(shù)的最大收益+不拿右子結(jié)點(diǎn)時(shí)右子樹(shù)的最大收益，即

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):

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

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

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

解72/87（2）如果s[i]≠s[j]，可以采用以下兩種操作使其變?yōu)榛匚模涸趕[j]后面添加一個(gè)字符s[i]（計(jì)一次操作），接下來(lái)只需要繼續(xù)考慮s[i+1..j]，對(duì)應(yīng)的操作次數(shù)=dp[i+1][j]+1。在s[i]前面添加一個(gè)字符s[j]（計(jì)一次操作），接下來(lái)只需要繼續(xù)考慮s[i..j-1]，對(duì)應(yīng)的操作次數(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 當(dāng)j<i+1時(shí)dp[i][j]=dp[i+1][j-1] 當(dāng)s[i]=s[j]dp[i][j]=min{dp[i+1][j]+1,dp[i][j-1]+1} 當(dāng)s[i]≠s[j]對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：74/87問(wèn)題描述：假設(shè)A是p×q矩陣，B是q×r矩陣，在計(jì)算C=A×B的標(biāo)準(zhǔn)算法中需要做pqr次數(shù)乘。給定n（n>2）個(gè)矩陣A1、A2、…、An，其中Ai和Ai+1（1≤i≤n-1）是可乘的，求這n個(gè)矩陣的乘積A1×A2×…×An時(shí)最少的數(shù)乘次數(shù)是多少？8.8.2矩陣連乘問(wèn)題75/87用一維數(shù)組p[0..n]表示n個(gè)矩陣的大小，p[0]表示A1的行數(shù)，p[i]表示Ai（1≤i≤n）的列數(shù)。例如，n=3，A1、A2和A3的大小分別為10×100、100×50和50×5。對(duì)應(yīng)的p[0..3]={10，100，50，5}。解76/87Ap×q×Bq×r的結(jié)果是矩陣Ap×r，需要做pqr次數(shù)乘。用A[i..j]表示Ai×…×Aj的連乘結(jié)果，其中Ai為p[i-1]×p[i]大小的矩陣，…，Aj為p[j-1]×p[j]大小的矩陣。則A[i..j]是一個(gè)p[i-1]×p[j]大小的矩陣。77/87采用區(qū)間動(dòng)態(tài)規(guī)劃方法求解。設(shè)計(jì)二維動(dòng)