《算法设计与分析基础》（Python语言描述） 课件 第8章动态规划2

8.1动态规划概述8.2一维动态规划CONTENTS提纲8.3二维动态规划8.4三维动态规划8.5字符串动态规划8.6背包动态规划8.7树形动态规划8.8区间动态规划第8章保存子问题解—动态规划1/878.5字符串动态规划字符串动态规划是指采用动态规划算法求解字符串的相关问题。说明2/87一个字符串的子序列是指从该字符串中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。给定两个字符串a和b，称字符串c是a和b的公共子序列，是指c同是a和b的子序列。该问题是求两个字符串a和b的最长公共子序列（LCS）。8.5.1最长公共子序列问题3/87设计二维动态规划数组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]状态转移方程在求出dp数组后，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): #循环处理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求一个最长公共子序列呢？分析状态转移方程最后两行的计算过程可以看出：若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是两个字符串。现在要用最少的字符操作次数（最优编辑距离），将字符串a编辑为字符串b。这里的字符编辑操作共有3种：删除一个字符，插入一个字符或者将一个字符替换另一个字符。例如，a="sfdqxbw"，b="gfdgw"，结果为4。8.5.2编辑距离11/87设计二维动态规划数组dp，其中dp[i][j]表示将a[0..i-1]（1≤i≤m）编辑为b[0..j-1]（1≤j≤n）的最优编辑距离（即最少编辑操作次数）。当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、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（一次替换操作的次数计为1）。在a[i-1]字符后面插入b[j-1]字符，有dp[i][j]=dp[i][j-1]+1（一次插入操作的次数计为1）。删除a[i-1]字符，有dp[i][j]=dp[i-1][j]+1（一次删除操作的次数计为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)] #二维动态规划数组4 foriinrange(1,m+1):5 dp[i][0]=i #把a的i个字符全部删除转换为b6 forjinrange(1,n+1):7 dp[0][j]=j #在a中插入b的全部字符转换为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背包动态规划背包动态规划主要指采用动态规划求解0/1背包问题、完全背包问题和多重背包问题及其类似的问题。说明16/87有n个编号为0～n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，每个物品要么选中要么不选中，即物品不能被分割，找到选中物品不仅能够放到背包中而且价值最大的方案。W=10物品编号重量w价值v026123265354446求解结果(最优方案)

选取的物品:014

总价值=158.6.10/1背包问题17/87

设置二维动态规划数组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状态转移方程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数组后dp[n][W]元素就是答案。20/871 defknap(w,v,n,W): #动态规划法求dp2 globaldp3 dp=[[0]*(W+1)foriinrange(n+1)] #二维动态规划数组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数组后，如何推导出一个解向量x=（x0，x1，…，xn-1）呢？从前面状态转移方程的后两行看出：若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): #回推求一个最优方案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算法空间优化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) #一维动态规划数组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) #一维动态规划数组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个整数的数组nums（1≤n≤20，0≤nums[i]≤1000）和一个整数target（-1000≤target≤1000）。向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造一个表达式。

例如，nums={2，1}，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式

“+2-1”。

设计一个算法求可以通过上述方法构造的运算结果等于target的不同表达式的数目。

要求设计如下方法：

def

findTargetSumWays(self,

nums,target)

->

int:8.6.2实战—目标和（LeetCode494★）29/87不妨用w表示nums数组，先求出w中所有整数和s，显然s<target时即使全部加上'+'也不可能成立，此时返回0（无解）。否则本问题就是求以下等式成立的不同表达式的数目（±表示取'+'或者'-'之一）：解用s减去两边后转换为：等同于：30/87对于

部分，如果取'-'（对应原来的'+'）则为0，如果取'+'（对应原来的'-'）则为2w[i]。考虑只取'-'的部分（其他取'+'），假设对应的下标为i1，i2，…，ik，则为：其中i1，i2，…，ik，是0，1，…，n-1的一个子序列，这样该问题等价于在w数组中选择添加'-'的元素和等于(s-target)/2的组合总数，属于典型的0/1背包问题。31/87

采用动态规划求解，设置二维动态规划数组dp，dp[i][r]表示在nums[0～i-1]（共i个整数）中选择若干整数添加'-'（其他添加'+'）并且和恰好为r的组合总数，对应的状态转移方程如下：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]的组合数之和)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]上述程序提交时通过，执行用时为100ms，内存消耗为15.1MB。34/87采用类似0/1背包问题的改进算法，设置一个一维动态规划设置dp，dp[r]表示选择整数和为r的组合总数。空间优化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]]

#组合总数是累计关系12

return

dp[W]上述程序提交时通过，执行用时为64ms，内存消耗为14.9MB。36/87有n种重量和价值分别为wi、vi（0≤i<n）的物品，从这些物品中挑选总重量不超过W的物品，每种物品可以挑选任意多件。求挑选物品的最大价值。8.6.3完全背包问题37/87设置动态规划二维数组dp，dp[i][r]表示从物品0～i-1（共i种物品）中选出重量不超过r的物品的最大总价值。显然有dp[i][0]=0（背包不能装入任何物品时，总价值为0），dp[0][j]=0（没有任何物品可装入时，总价值为0），将它们作为边界情况，为此一次性将dp数组初始化为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另外设置二维数组fk，其中fk[i][r]存放dp[i][r]得到最大值时物品i-1挑选的件数。考虑物品i-1，可以选择0到k（k×w[i-1]≤r）次。39/87状态转移方程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）最优方案：物品2挑选2件，物品1挑选0件，物品0挑选1件。40/871 defcompleteknap(w,v,n,W): #采用动态规划方法求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(): #回推求一个最优选择方案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算法中包含三重循环，k的循环最坏可能从0到W，所以算法的时间复杂度为O(nW2)。42/87算法时间优化将完全背包问题转换为这样的0/1背包问题，物品i出现

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] #返回总价值【算法分析】上述算法中包含两重循环，所以算法的时间复杂度为O(nW)。44/87算法空间优化1 defcompleteknap2(w,v,n,W): #空间改进算法2 dp=[0]*(W+1) #一维动态规划数组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) #一维动态规划数组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个整数的数组coins，表示不同面额的硬币，以及一个表示总金额的整数amount。设计一个算法求可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额则返回-1

。可以认为每种硬币的数量是无限的。

例如，coins={1，2，5}，amount=11，对应的硬币组合是1，5，5，答案为3。

要求设计如下方法：

def

coinChange(self,coins,amount)

->

int:8.6.4实战—零钱兑换（LeetCode332）46/87由于每种硬币的数量是无限的，该问题转换为完全背包问题，只是这里求最少的硬币个数，相当于每个硬币的价值为1，并且将max改为min。采用改进的完全背包动态规划算法，设置一维动态规划设置dp，dp[r]表示总金额为r的最少的硬币个数。另外考虑特殊情况，将dp所有元素初始化为∞，当最后出现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)

#一维动态规划数组,初始化为∞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上述程序提交时通过，执行用时执行用时12ms，内存消耗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，一个最优方案是选择物品0和1各一件。50/87设置动态规划二维数组dp，dp[i][r]表示从物品0～i-1（共i个物品）中选出重量不超过r的物品的最大总价值，选择物品i的最多件数为s[i]。解51/871 defmultiknap(w,v,n,W): #求解多重背包问题2 globaldp3 dp=[[0]*(W+1)foriinrange(n+1)]

#二维动态规划数组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树形动态规划树形动态规划指基于树结构（含二叉树）的动态规划算法设计。由于树具有严格的分层，使得动态规划的阶段十分清晰，例如父子结点的关系可能就是两个阶段之间的联系。树形动态规划涉及树的搜索，通常采用深度优先搜索。说明53/87【例8-2】某学校要开一个庆祝晚会，学校共有n个员工，员工编号为1～n，员工之间有上下级关系，这样构成一棵关系树结构。为了让员工开心，晚会组织者决定不会同时邀请一个员工和他的直属上级。每个员工参加晚会有一个开心指数，用整型数组value表示，value[i]表示员工i的开心指数。问题是求参加晚会的所有员工开心指数和的最大值，给出采用动态规划求解的思路。54/87采用树形动态规划方法求解，树中每个结点表示一个员工，每个员工有两种状态，即参加和不参加庆祝晚会。为此设计二维动态规划数组dp来描述状态（初始时所有元素设置为0），其中dp[i][1]表示员工i参加庆祝晚会时对应子树的最大开心指数和，dp[i][0]表示员工i不参加庆祝晚会时对应子树的最大开心指数和。解55/87（1）员工i有下级员工，员工i有参加和不参加晚会两种可能。

①员工i参加晚会，那么他的所有下级员工都不能参加，则结点i子树的最大开心指数和为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子树的最大开心指数和为dp[i][0]，即取员工i的所有下级员工参加和不参加的最大开心指数和的最大值，然后累计起来，如图(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子树的最大开心指数和为dp[i][1]，有：

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

②员工i不参加庆祝晚会，则结点i子树的最大开心指数和为dp[i][0]，有：dp[i][0]=0在求出dp数组后，对于根结点root，则max(dp[root][0]，dp[root][1])就是最后的答案。对于员工i的各种情况分析如下：58/87问题描述：有一个矿洞由多个矿区组成，每个矿区有若干煤炭，矿洞只有一个入口，称之为根。除了根之外，每个矿区有且只有一个父矿区与之相连。所有矿区的排列类似于一棵二叉树。

A进入矿洞想找到尽可能多的煤炭，由于某种原因A不能在同一天晚上拿走两个直接相连矿区的煤炭。求A一晚能够拿走的最多煤炭。

例如，一个矿洞结构如下图所示，二叉树结点中的数字表示煤炭数量，A一晚能够拿走的最多煤炭=3+3+1=7。323138.7.2实战—找矿（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={}

#定义哈希表作为动态规划数组3

def

rob(self,

root:

Optional[TreeNode])

->

int:4

if

root==None:return

05

return

self.dfs(root)采用备忘录方法，用哈希映射将字典对象hmap存储已经求出的子问题解，以消除重复计算，也就是说若结点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，有拿和不拿两种可能。设计一维动态规划数组dp[2]，其中dp[0]表示不拿结点root的最大收益，dp[1]表示拿结点root的最大收益，其左右子树的动态规划数组分别用ldp[]和rdp[]表示。解法2—动态规划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):

#动态规划算法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实战—监控二叉树（LeetCode968★★★）自学(老师讲的太多了)69/878.8区间动态规划区间动态规划通常以连续区间的求解作为子问题，例如区间[i,j]上的最优解用dp[i][j]表示。先在小区间上进行动态规划得到子问题的最优解，然后再利用小区间的最优解合并产生大区间的最优解。区间动态规划一般需要从小到大枚举所有可能的区间，在枚举时不能够像平常的从头到尾遍历，而是以区间的长度len为循环变量，在不同的长度区间里枚举所有可能的状态，并从中选取最优解。合并操作一般是把左、右两个相邻的子区间合并。说明70/87【例8-3】给定一个字符串s，每一次操作可以在s的任意位置插入任意字符。求让s成为回文串的最少操作次数，给出对应的状态转移方程。71/87

设置二维动态规划设置dp，dp[i][j]表示将子串s[i..j]（含s[i]和s[j]字符）变成回文串的最少操作次数（每次操作添加一个字符）。

（1）如果s[i]=s[j]，那么最外层已经形成了回文，接下来只需要继续考虑s[i+1..j-1]，即dp[i][j]=dp[i+1][j-1]。

解72/87（2）如果s[i]≠s[j]，可以采用以下两种操作使其变为回文：在s[j]后面添加一个字符s[i]（计一次操作），接下来只需要继续考虑s[i+1..j]，对应的操作次数=dp[i+1][j]+1。在s[i]前面添加一个字符s[j]（计一次操作），接下来只需要继续考虑s[i..j-1]，对应的操作次数=dp[i][j-1]+1。

两种操作中取最小操作次数，即

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]对应的状态转移方程如下：74/87问题描述：假设A是p×q矩阵，B是q×r矩阵，在计算C=A×B的标准算法中需要做pqr次数乘。给定n（n>2）个矩阵A1、A2、…、An，其中Ai和Ai+1（1≤i≤n-1）是可乘的，求这n个矩阵的乘积A1×A2×…×An时最少的数乘次数是多少？8.8.2矩阵连乘问题75/87用一维数组p[0..n]表示n个矩阵的大小，p[0]表示A1的行数，p[i]表示Ai（1≤i≤n）的列数。例如，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次数乘。用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采用区间动态规划方法求解。设计二维动