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

第8章保存子问题解—动态规划8.1动态规划概述8.2一维动态规划CONTENTS提纲8.3二维动态规划8.4三维动态规划8.5字符串动态规划8.6背包动态规划8.7树形动态规划8.8区间动态规划1/918.1动态规划概述动态规划将要解决的问题转化为一系列的子问题并且逐步加以解决，将前面解决子问题的结果作为后续解决子问题的条件，并且避免无意义的穷举。说明2/918.1.1从一个简单示例入门【例8-1】一个楼梯有n（1≤n≤100）个台阶，上楼可以一步上1个台阶，也可以一步上2个台阶，设计一个算法求上楼梯共有多少种不同的走法。3/91解设f(n)表示上n个台阶的楼梯的走法数，显然，f(1)=1，f(2)=2（一种走法是一步上1个台阶、走2步，另外一种走法是一步上2个台阶）。对于大于2的n个台阶的楼梯：一种走法是第一步上1个台阶，剩余n-1个台阶的走法数是f(n-1)；另外一种走法是第一步上2个台阶，剩余n-2个台阶的走法数是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调用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数组，用dp[i]存放f1(i)的值。递归算法6/91上述算法2采用递归算法，可以直接采用迭代实现，仍然设计一维dp数组，用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就是动态规划算法，其中数组dp（表）称为动态规划数组，从中看出动态规划就是记录子问题的结果再利用的方法。原问题子问题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]中滚动数组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动态规划的原理一个多段图G=（V，E），在顶点0处有一水库，现需要从顶点0铺设一条管道到顶点9，边上的数字表示对应两个顶点之间的距离，该图采用邻接矩阵A表示。现要找出一条从顶点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可能有多个状态，通常用状态集合Sk表示，例如S1={1，2，3}。状态变量xk表示Sk中某个状态，如x1可以取S1中的任意值。12/91动态规划中当前阶段的状态往往是上一阶段状态和相应决策的结果，采用指标函数表示它们之间关系称为状态转移方程，指标函数通常是最优解函数。设最优解函数f(s)为状态s到终点9的最短路径长度，用k表示阶段。13/91状态转移方程：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也可以设最优解函数f(s)为起点0到状态s的最短路径长度状态转移方程：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动态规划求解问题的性质和步骤最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优性原理。无后效性：如果某个阶段状态一旦确定，就不受以后决策的影响，也就是说某个状态以后的决策不会影响以前的状态。重叠子问题：一个问题分解的若干子问题之间是不独立的，其中一些子问题在后面的决策中可能被多次重复使用。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。采用动态规划求解的问题一般要具有以下3个性质22/91确定状态：将问题求解中各个阶段所处的各种情况用不同的状态表示出来。确定状态转移方程：描述求解中各个阶段的状态转移和指标函数的关系。确定初始条件和边界情况：状态转移方程通常是一个递推式，初始条件通常指定递推的起点，在递推中需要考虑一些特殊情况，称为边界情况。确定计算顺序：也就是指定求状态转移方程的顺序，是顺序求解还是逆序求解。消除冗余：如采用滚动数组进一步提高时空性能。一般来说动态规划算法设计要经历以下几个步骤23/918.1.4动态规划与其他方法的比较动态规划的基本思想与分治法类似，也是将求解的问题分解为若干个子问题（阶段），按照一定的顺序求解子问题，前一个子问题的解有助于后一个子问题的求解。但分治法中各个子问题是独立的（不重叠），而动态规划适用于子问题重叠的情况。动态规划又和贪心法有些相似，都需要满足最优子结构性质，都是将一个问题的解决方案视为一系列决策的结果。不同的是贪心法每次采用贪心选择便做出一个不可回溯的决策，而动态规划算法中隐含有回溯的过程。24/918.2一维动态规划一维动态规划是指设计动态规划算法中采用一维动态规划数组，也称为线性动态规划。说明25/91给定一个含n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。序列（-2，11，-4，13，-5，-2）的最大连续子序列和为20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大连续子序列和为16。规定一个序列最大连续子序列和至少是0，如果小于0，其结果为0。8.2.1最大连续子序列和26/91解dp[0]=a[0] 初始条件dp[i]=max(dp[i-1]+ai，ai) i>0

设计一维动态规划dp，dp[i]（0≤i≤n-1）表示以元素ai结尾的最大连续子序列和，显然dp[i-1]表示以元素ai-1结尾的最大连续子序列和。判断ai分为两种情况：将ai合并到前面以元素ai-1结尾的最大连续子序列中，此时有dp[i]=dp[i-1]+ai。不将ai合并到前面以元素ai-1结尾的最大连续子序列中，即从ai开始构造一个连续子序列，此时有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。由于本题中最大连续子序列和至少为0（或者说最大连续子序列可以为空序列），所以最后的最大连续子序列和应该为max(ans，0)。28/911 defmaxSubSum(a): #求最大连续子序列和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数组中求出最大元素的序号maxi，i从maxi序号开始在a中向前查找，rsum从dp[maxi]开始递减a[i]，直到rsum为0，对应的a中子序列就是一个最大连续子序列。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后推导出一个最大连续子序列30/911 defmaxSub(a): #求一个最大连续子序列2 n=len(a)3 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空间优化如果只需要求最大连续子序列和，可以采用滚动数组优化空间。maxSubSum算法中用j标识阶段，由于dp[j]仅仅与dp[j-1]相关，将一维dp数组改为单个变量dp。1 defmaxSubSum1(a): #求最大连续子序列和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）个整数的数组

nums（整数值在-100000到100000之间），找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如nums={-2,-1}，结果为-1。

要求设计如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int:8.2.2实战—最大子序和（LeetCode53★）33/91解本题采用动态规划求解的原理见8.2.1节，这里仅仅需要求最大连续子序列和，而且该最大连续子序列至少含一个元素。采用滚动数组。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上述程序提交时通过，执行用时为172ms，内存消耗为30MB。35/91问题描述：给定一个无序的整数序列a[0..n-1]，求其中最长递增（严格）子序列的长度。例如，a={2，1，5，3，6，4，8，9，7}，n=9，其最长递增子序列为{1，3，4，8，9}，结果为5。8.2.3最长递增子序列36/91解dp[i]表示以a[i]结尾的最长递增子序列的长度。计算顺序是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结尾的最长递增子序列加上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数组后，通过顺序遍历dp求出最大值ans，则ans就是最长递增（严格）子序列的长度。38/91状态转移方程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数组中求出最大元素的序号maxj，置j=maxj，prej从j的前一个序号开始在a中向前查找，rnum从dp[maxj]开始，若a[prej]<a[j]置rnum--，直到rnum为0，对应的a中子序列就是一个最大连续子序列。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] #剩余的元素个数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个活动和一个资源，每个活动执行时都要占用该资源，并且该资源任何时刻只能被一个活动所占用，一旦某个活动开始执行，中间不能被打断，直到其执行完毕。每个活动i有一个开始时间bi和结束时间ei（bi<ei），它是一个半开时间区间[bi，ei），其占用资源的时间=ei-bi。假设最早活动执行时间为0。求一种最优活动安排方案，使得安排的活动的总占用时间最长。8.2.4*活动安排问题Ⅱ43/91解该问题与7.2.1节的活动安排问题Ⅰ类似，不同的是这里求一个总占用时间最长的兼容活动子集，而不是求活动个数最多的兼容活动子集，两者是不同的。这里采用贪心法+动态规划的思路，先求出每个活动A[i]的占用资源的时间A[i].length=A[i].e-A[i].b，将活动数组A[0..n-1]按结束时间递增排序（贪心思路）。44/9111个活动（已按结束时间的递增排列）活动i012345678910开始时间130535688212结束时间4567891011121315ans=1345/91设计一维动态规划数组dp，dp[i]表示A[0..i]（共i+1个活动）中所有兼容活动的最长占用时间。考虑活动i，找到前面与之兼容的最晚的活动j，即，称活动j为活动i的前驱活动。如果活动i找到了前驱活动j，可以有两种选择：①活动j之后不选择活动i，此时dp[i]=dp[i-1]。②活动j之后选择活动i，此时dp[i]=dp[j]+A[i].length。两种情况中取最大值。对应的状态转移方程如下：dp[0]=活动0的时间

边界情况dp[i]=max{dp[i-1]，dp[j]+A[i].length} 活动j是活动i的前驱46/91

求出dp数组后，dp[n-1]就是最长的总占用时间。为了求一个最优安排方案，设计一个一维数组pre，pre[i]的含义如下：①若活动i没有前驱活动，置pre[i]=-2。②若活动i有前驱活动j，但不选择活动i，置pre[i]=-1。③若活动i有前驱活动j，选择活动i，置pre[i]=j。47/911 classAction: #活动类2 def__init__(self,b,e):3 self.b=b #活动起始时间4 self.e=e #活动结束时间5 self.length=e-b #求每个活动的占用时间6 def__lt__(self,other): #用于按e递增排序7 ifself.e<other.e:returnTrue8 else:returnFalse48/9110 defplan(A): #动态规划算法求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没有前驱活动49/9118 foriinrange(1,n):19 j=i-120 whilej>=0andA[j].e>A[i].b:j-=1

#找活动i的前驱j21 ifj==-1: #活动i前面没有兼容22 dp[i]=A[i].length23 pre[i]=-2 #活动i没有前驱24 else: #活动i存在前驱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,前驱为j31 returndp[n-1]50/91【算法分析】主要时间花费在查找前驱活动上，对应的时间复杂度为O(n2)。51/911 defgetx(n): #求一个最优方案2 x=[] #存放一个方案3 i=n-1 #从n-1开始4 whileTrue:5 ifi==-2:break #已经没有前驱活动了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结束时间4567891011121315length326254434113dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-2853/91求一个最优安排方案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说明没有前驱活动，结束x={2,6,10}1354/918.3二维动态规划二维动态规划是指设计动态规划算法中采用二维动态规划数组，也称为坐标型动态规划。说明55/91给定一个高度为n的整数三角形，求从顶部到底部的最小路径和及其一条最小路径，从每个整数出发只能向下移动到相邻的整数。例如，一个n=4的三角形，输出的最小路径和是13，一条最小路径是2，3，5，3。23472659838.3.1三角形最小路径和56/91解问题求解—自顶向下2347265983i-1,ji-1,j-1i,jJI234726598357/91

设计数组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数组的第n-1行中求出的最小元素ans=dp[n-1][minj]。60/911 defminPathSum(a): #自顶向下求最小路径和2 n=len(a)3 dp=[[0]*nforiinrange(n)] #二维动态规划数组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): #考虑其他有两条达到路径的结点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那么如何找到一条最小和的路径呢？设计一个二维数组pre，pre[i][j]表示到达（i，j）位置时最小路径上的前驱位置，由于前驱位置只有两个即（i-1，j-1）和（i-1，j），用pre[i][j]记录前驱位置的列号即可。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)] #二维动态规划数组4 pre=[[0]*nforiinrange(n)] #二维路径数组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): #两条达到路径的结点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

设计二维动态规划数组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)] #二维动态规划数组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自底向上算法空间优化在自底向上算法中阶段i（指求第i行的dp）仅仅与阶段i+1相关，采用降维滚动数组方式，将dp由二维数组改为一维数组。dp[*][j]dp[j]i+1,j+1i+1,ji，

jJI234726598371/911 defminPathSum3(a): #自底向上的优化算法2 n=len(a)3 dp=[0]*n #一维动态规划数组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实战—下降路径最小和（LeetCode931★★）问题描述：给定一个n×n的整数数组

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]。上述各式合起来构成状态转移方程，由其求出dp数组，那么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)]

#二维动态规划数组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自上而下算法空间优化由于dp[i]仅仅与dp[i-1]相关，采用滚动数组方法，将dp数组大小改为dp[2][n]：用dp[0][j]存放dp[i-1][j]，用dp[1][j]存放dp[i][j]。通过变量c实现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)]

#二维动态规划数组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上述代码提交时通过，执行用时为56ms，内存消耗为15.8MB。自下而上的动态规划算法自学82/918.4三维动态规划三维动态规划是指设计动态规划算法中采用三维动态规划数组。说明83/91设计二维数组B存放当前顶点之间的最短路径长度，其中B[i][j]表示当前顶点i到j的最短路径长度。依顶点编号顺序处理每个顶点，每个顶点的处理看作一个阶段，阶段k