算法设计与分析 思政课件 第8、9章 动态规划、NP完全问题

第8章动态规划8.1动态规划概述8.2一维动态规划CONTENTS提纲8.3二维动态规划8.4三维动态规划8.5字符串动态规划8.6背包动态规划8.7树形动态规划8.8区间动态规划1/878.1动态规划概述动态规划将要解决的问题转化为一系列的子问题并且逐步加以解决，将前面解决子问题的结果作为后续解决子问题的条件，并且避免无意义的穷举。2/87说明8.1.1从一个简单示例入门【例8-1】一个楼梯有n（1≤n≤100）个台阶，上楼可以一步上1个台阶，也可以一步上2个台阶，设计一个算法求上楼梯共有多少种不同的走法。3/87解设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/87intf1(intn) //算法1{ if(n==1)return1; elseif(n==2)return2; elsereturnf1(n-2)+f1(n-1);}f1(5)f1(3)f1(4)f1(1)f1(2)f1(3)f1(1)f1(2)f1(2)存在大量重复的子问题5/87intdp[MAXN];intf21(intn) //被f2函数调用{ if(dp[n]!=0)returndp[n]; if(n==1)dp[n]=1; elseif(n==2)dp[n]=2; elsedp[i]=f21(i-2)+f21(i-1); returndp[n];}intf2(intn) //算法2{ memset(dp,0,sizeof(dp)); returnf21(n);}如何避免重叠子问题的重复计算呢？可以设计一个一维dp数组，用dp[i]存放f1(i)的值。6/87上述算法2采用递归算法，可以直接采用迭代实现，仍然设计一维dp数组，用dp[i]存放f1(i)的值。intf3(intn) //算法3{ intdp[MAXN]; dp[1]=1; dp[2]=2; for(inti=3;i<=n;i++) dp[i]=dp[i-2]+dp[i-1]; returndp[n];}7/87上述算法3就是动态规划算法，其中数组dp（表）称为动态规划数组，从中看出动态规划就是记录子问题的结果再利用的方法。原问题子问题1子问题2子问题k…表原问题的解8/87f(1)f(n-2)f(n-1)f(n)…f(n)=f(n-2)+f(n-1)intf4(intn) //算法4{ intdp[3];

dp[0]=1;dp[1]=2; for(inti=2;i<n;i++)

dp[i%3]=dp[(i-1)%3]+dp[(i-2)%3]; returndp[(n-1)%3];}9/87最常见的算法intf5(intn) //算法5{ if(n==1)return1; elseif(n==2)return2; else { inta=1,b=2,c; for(inti=3;i<=n;i++) { c=a+b; a=b;b=c; } returnc; }}10/878.1.2动态规划的原理一个多段图G=（V，E），在顶点0处有一水库，现需要从顶点0铺设一条管道到顶点9，边上的数字表示对应两个顶点之间的距离，该图采用邻接矩阵A表示。现要找出一条从顶点0到顶点9的线路，使得铺设的管道长度最短。5343343633474236242012345678911/8753433436334742362420123456789阶段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/87动态规划中当前阶段的状态往往是上一阶段状态和相应决策的结果，采用指标函数表示它们之间关系称为状态转移方程，指标函数通常是最优解函数。设最优解函数f(s)为状态s到终点9的最短路径长度，用k表示阶段。状态转移方程：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到013/87从k=3开始直到k=0为止，f0(0)就是最短管道长度，称为逆序解法。设计二维动态规划数组dp[K][MAXN]，dp[k][s]表示fk(s)的结果，起始点start=0，终点end=9。05343343633474236242012345678934676119912f4(9)=0fk(s)=min<s,t>∈E{A[s][t]+fk+1(t)} k从3到014/87也可以设最优解函数f(s)为起点0到状态s的最短路径长度状态转移方程：f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k从1到415/8753433436334742362420123456789108758243012这样求解过程是从k=1开始直到k=4为止，f4(9)就是最短管道长度，称为顺序解法。f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k从1到416/878.1.3动态规划求解问题的性质和步骤最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优性原理。无后效性：如果某个阶段状态一旦确定，就不受以后决策的影响，也就是说某个状态以后的决策不会影响以前的状态。重叠子问题：一个问题分解的若干子问题之间是不独立的，其中一些子问题在后面的决策中可能被多次重复使用。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。采用动态规划求解的问题一般要具有以下3个性质17/87确定状态：将问题求解中各个阶段所处的各种情况用不同的状态表示出来。确定状态转移方程：描述求解中各个阶段的状态转移和指标函数的关系。确定初始条件和边界情况：状态转移方程通常是一个递推式，初始条件通常指定递推的起点，在递推中需要考虑一些特殊情况，称为边界情况。确定计算顺序：也就是指定求状态转移方程的顺序，是顺序求解还是逆序求解。消除冗余：如采用滚动数组进一步提高时空性能。一般来说动态规划算法设计要经历以下几个步骤18/878.1.4动态规划与其他方法的比较动态规划的基本思想与分治法类似，也是将求解的问题分解为若干个子问题（阶段），按照一定的顺序求解子问题，前一个子问题的解有助于后一个子问题的求解。但分治法中各个子问题是独立的（不重叠），而动态规划适用于子问题重叠的情况。动态规划又和贪心法有些相似，都需要满足最优子结构性质，都是将一个问题的解决方案视为一系列决策的结果。不同的是贪心法每次采用贪心选择便做出一个不可回溯的决策，而动态规划算法中隐含有回溯的过程。19/878.2一维动态规划一维动态规划是指设计动态规划算法中采用一维动态规划数组，也称为线性动态规划。20/87说明8.2.1最大连续子序列和给定一个含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。21/87解dp[0]=a[0] 初始条件dp[i]=max(dp[i-1]+ai，ai) i>022/87

设计一维动态规划dp，dp[i]（1≤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。ans=dp[3]=20dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2max求出dp中的最大元素ans。由于本题中最大连续子序列和至少为0（或者说最大连续子序列可以为空序列），所以最后的最大连续子序列和应该为max(ans，0)。23/87intdp[MAXN];intmaxSubSum(vector<int>&a) //求最大连续子序列和{ intn=a.size(); memset(dp,0,sizeof(dp));

dp[0]=a[0]; for(inti=1;i<n;i++) //计算顺序是j从1到n-1

dp[i]=max(dp[i-1]+a[i],a[i]); intans=dp[0]; for(inti=1;i<n;i++) ans=max(ans,dp[i]); returnmax(ans,0);}【算法分析】maxSubSum算法含两个for循环（实际上第二个for循环可以合并到第一个for循环中），对应时间复杂度均为O(n)。算法中应用了dp数组，对应的空间复杂度为O(n)。24/87当求出dp后可以推导出一个最大连续子序列（实际上这样的最大连续子序列可能有多个，这里仅仅求出其中的一个）。先在dp数组中求出最大元素的序号maxi，i从maxi序号开始在a中向前查找，rsum从dp[maxi]开始递减a[i]，直到rsum为0，对应的a中子序列就是一个最大连续子序列。i=maxi=3rsum=7dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2逆置maxi=2rsum=11i=1rsum=0{11，-4，13}25/8726/87vector<int>maxSub(vector<int>&a) //求一个最大连续子序列{ intn=a.size(); vector<int>x; intmaxi=0; for(inti=1;i<n;i++) //求dp中最大元素序号maxi if(dp[i]>dp[maxi]) maxi=i; intrsum=dp[maxi]; inti=maxi; while(i>=0&&rsum!=0) { rsum-=a[i]; x.push_back(a[i]); i--; }

reverse(x.begin(),x.end()); returnx;}空间优化如果只需要求最大连续子序列和，可以采用滚动数组优化空间。maxSubSum算法中用j标识阶段，由于dp[j]仅仅与dp[j-1]相关，将一维dp数组改为单个变量dp。intmaxSubSum1(vector<int>&nums) //求最大连续子序列和{ intn=nums.size(); intdp;

dp=nums[0]; intans=dp; for(inti=1;i<n;i++) //计算顺序是i从1到n-1循环 { dp=max(dp+nums[i],nums[i]); ans=max(ans,dp); } returnmax(ans,0);}空间复杂度为O(1)27/878.2.2实战—最大子序和（LeetCode53）问题描述:给定一个含n（1≤n≤30000）个整数的数组

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

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

要求设计如下函数：classSolution{public:intmaxSubArray(vector<int>&nums){}};28/87解本题采用动态规划求解的原理见8.2.1节，这里仅仅需要求最大连续子序列和，而且该最大连续子序列至少含一个元素。采用滚动数组。29/87classSolution{public: intmaxSubArray(vector<int>&nums) { intn=nums.size(); if(n==1)returnnums[0]; intdp; dp=nums[0]; intans=dp; for(intj=1;j<n;j++) { dp=max(dp+nums[j],nums[j]);

ans=max(ans,dp); } returnans; //不能改为max(ans,0) }};30/878.2.3最长递增子序列问题描述：给定一个无序的整数序列a[0..n-1]，求其中最长递增（严格）子序列的长度。例如，a={2，1，5，3，6，4，8，9，7}，n=9，其最长递增子序列为{1，3，4，8，9}，结果为5。31/87解dp[i]表示以a[i]结尾的子序列a[0..i]（共i+1个元素）中的最长递增子序列的长度。计算顺序是i从0到n-1，对于每个a[i]，dp[i]置为1（表示只有a[i]一个元素时最长递增子序列的长度为1）。32/87考虑a[0..i-1]中的每一个元素a[j]，分为两种情况：若a[j]<a[i]，则以aj结尾的最长递增子序列加上ai可能构成一个更长的递增子序列，此时有dp[i]=max(dp[i]，dp[j]+1)。a0

a1

aj

…

ai-1

ai

…

an-1dp[j]dp[i]=max(dp[i],dp[j]+1)aj<ai否则最长递增子序列没有改变。在求出dp数组后，通过顺序遍历dp求出最大值ans，则ans就是最长递增（严格）子序列的长度。33/87状态转移方程dp[i]=1 0≤i≤n-1（初始条件）dp[i]=maxa[j]<a[i](j<i){dp[j]+1} 0≤i≤n-134/87intmaxInclen(vector<int>&a) //求最长递增子序列长度{ intn=a.size(); for(inti=0;i<n;i++) { dp[i]=1; for(intj=0;j<i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } } intans=dp[0]; for(inti=1;i<n;i++) ans=max(ans,dp[i]); returnans;}【算法分析】时间复杂度为O(n2)，空间复杂度为O(n)。35/87当求出dp后可以推导出一个最长递增子序列。先在dp数组中求出最大元素的序号maxj，置j=maxj，prej从j的前一个序号开始在a中向前查找，rnum从dp[maxj]开始，若a[prej]<a[j]置rnum--，直到rnum为0，对应的a中子序列就是一个最大连续子序列。a0

a1

aj

…

ai-1

ai

…

an-1maxjdp[i]=max(dp[i],dp[[j]+1)aj<ai36/87vector<int>maxInc(vector<int>&a) //求一个最长递增子序列{ intn=a.size(); vector<int>x; intmaxj=0; for(intj=1;j<n;j++) if(dp[j]>dp[maxj])maxj=j;

x.push_back(a[maxj]); intrnum=dp[maxj]-1; //剩余的元素个数 intj=maxj; //j指向当前最长递增子序列的一个元素 intprej=maxj-1; //prej查找最长递增子序列的前一个元素 while(prej>=0&&rnum!=0) { if(a[prej]<a[j]) { rnum--;

x.push_back(a[prej]); j=prej;prej--; } elseprej--; } reverse(x.begin(),x.end()); returnx;}37/878.2.4*活动安排问题Ⅱ假设有n个活动和一个资源，每个活动执行时都要占用该资源，并且该资源任何时刻只能被一个活动所占用，一旦某个活动开始执行，中间不能被打断，直到其执行完毕。每个活动i有一个开始时间bi和结束时间ei（bi<ei），它是一个半开时间区间[bi，ei），其占用资源的时间=ei-bi。假设最早活动执行时间为0。求一种最优活动安排方案，使得安排的活动的总占用时间最长。38/8711个活动（已按结束时间的递增排列）活动i012345678910开始时间130535688212结束时间456789101112131539/87解该问题与7.2.1节的活动安排问题Ⅰ类似，不同的是这里求一个总占用时间最长的兼容活动子集，而不是求活动个数最多的兼容活动子集，两者是不同的。这里采用贪心法+动态规划的思路，先求出每个活动A[i]的占用资源的时间A[i].length=A[i].e-A[i].b，将活动数组A[0..n-1]按结束时间递增排序（贪心思路）。40/87设计一维动态规划数组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的前驱活动41/87

求出dp数组后，dp[n-1]就是最长的总占用时间。为了求一个最优安排方案，设计一个一维数组pre，pre[i]的含义如下：①若活动i没有前驱活动，置pre[i]=-2。②若活动i有前驱活动j，但不选择活动i，置pre[i]=-1。③若活动i有前驱活动j，选择活动i，置pre[i]=j。42/8711个活动求出的dp和pre如下所示。dp[10]=13活动i012345678910开始时间130535688212结束时间4567891011121315length326254434113dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-2843/87structAction

//活动的类型{ intb,e; //开始时间和结束时间 intlength; //活动的占用时间 booloperator<(constActiont)const { returne<t.e; //按结束时间递增排序 }};intn=11; //活动个数ActionA[MAXN]={{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,15}};intdp[MAXN]; //一维动态规划数组intpre[MAXN]; //pre[i]存放前驱活动序号44/87intplan() //求解算法{ memset(dp,0,sizeof(dp)); //dp数组初始化

sort(A,A+n);

//排序

dp[0]=A[0].length;

pre[0]=-2;

//活动0没有前驱活动 for(inti=1;i<n;i++) { intj=i-1; while(j>=0&&A[j].e>A[i].b) j--; //在A[0..i-1]找与活动i兼容的最晚活动j if(j==-1) //活动i前面没有兼容活动 { dp[i]=A[i].length;

pre[i]=-2;

//表示没有前驱活动 }45/87 else //活动i前面有最晚兼容活动j { if(dp[i-1]>=dp[j]+A[i].length) //dp[i]=max(dp[i-1],dp[j]+A[i].length) { dp[i]=dp[i-1];

pre[i]=-1;

//不选择活动i } else { dp[i]=dp[j]+A[i].length;

pre[i]=j;

//选中活动i,前驱活动为活动j } } } returndp[n-1]; //返回最优解}【算法分析】主要时间花费在排序上，对应的时间复杂度为O(nlog2n)。46/87求一个最优安排方案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[6]=2活动6√

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

xi=pre[2]=-2i=-2说明没有前驱活动，结束pre[7]=-1活动7×

i减1

i=647/87voidgetx() //求一个最优安排方案{ vector<int>x; //存放一个方案 inti=n-1; //从n-1开始 while(true) { if(i==-2) //活动i没有前驱活动 break; if(pre[i]==-1) //不选择活动i i--; else //选择活动i { x.push_back(i); i=pre[i]; } } printf("选择的活动:"); //输出结果 for(inti=x.size()-1;i>=0;i--) printf("%d[%d,%d]",x[i],A[x[i]].b,A[x[i]].e); printf("\n"); printf("最长占用时间:%d\n",dp[n-1]);}48/878.3二维动态规划二维动态规划是指设计动态规划算法中采用二维动态规划数组，也称为坐标型动态规划。49/87说明8.3.1三角形最小路径和给定一个高度为n的整数三角形，求从顶部到底部的最小路径和及其一条最小路径，从每个整数出发只能向下移动到相邻的整数。例如，一个n=4的三角形，输出的最小路径和是13，一条最小路径是2，3，5，3。234726598350/87解问题求解—自顶向下2347265983i-1，ji-1，j-1i，jJI234726598351/87

设计二维动态规划数组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]。

其他两条到达（i，j）位置的路径，最小路径和dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]。i-1,ji-1,j-1i，jJI52/87dp[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]。53/87intminPathSum(vector<vector<int>>&a) //自顶向下求最小路径和{ intn=a.size(); dp[0][0]=a[0][0]; for(inti=1;i<n;i++) //考虑第0列的边界

dp[i][0]=dp[i-1][0]+a[i][0]; for(inti=1;i<n;i++) //考虑对角线的边界

dp[i][i]=a[i][i]+dp[i-1][i-1]; for(inti=2;i<n;i++) //考虑其他有两条达到的路径 { for(intj=1;j<i;j++)

dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } intans=dp[n-1][0]; for(intj=1;j<n;j++) //求出最小ans ans=min(ans,dp[n-1][j]); returnans;}54/87那么如何找到一条最小和的路径呢？设计一个二维数组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]=j55/87在求出ans后，通过pre[n-1][minj]推导求出反向路径path，逆向输出得到一条最小和的路径。voidminPathSum1(vector<vector<int>>&a) //求最小路径和以及一条最小和路径{ intpre[MAXN][MAXN]; //路径数组 intn=a.size(); dp[0][0]=a[0][0]; for(inti=1;i<n;i++) //考虑第0列的边界 { dp[i][0]=dp[i-1][0]+a[i][0];

pre[i][0]=0; } for(inti=1;i<n;i++) //考虑对角线的边界 { dp[i][i]=a[i][i]+dp[i-1][i-1];

pre[i][i]=i-1; }56/87i-1，0i，0pre[i][j]=0i-1，i-1i，ipre[i][i]=i-1 for(inti=2;i<n;i++) //考虑其他有两条达到路径的结点 { for(intj=1;j<i;j++) { if(dp[i-1][j-1]<dp[i-1][j]) { pre[i][j]=j-1;

dp[i][j]=a[i][j]+dp[i-1][j-1]; } else { pre[i][j]=j;

dp[i][j]=a[i][j]+dp[i-1][j]; } } }57/87i-1，ji-1，j-1i，jpre[i][j]=j-1i-1，ji-1，j-1i，jpre[i][j]=j intans=dp[n-1][0]; intminj=0; for(intj=1;j<n;j++) //求出最小ans和对应的列号minj { if(ans>dp[n-1][j]) { ans=dp[n-1][j];

minj=j; } } printf("最小路径和ans=%d\n",ans); inti=n-1; vector<int>path; //存放一条路径 while(i>=0) //从(n-1,minj)位置推导反向路径 { path.push_back(a[i][minj]);

minj=pre[i][minj];

//最小路径在前一行中的列号 i--; //在前一行查找 } printf("最小路径:"); for(inti=path.size()-1;i>=0;i--) //反向输出path printf("%d",path[i]); printf("\n");}58/87问题求解—自底向上i+1，j+1i+1，ji，

jJI234726598359/87

设计二维动态规划数组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]。

其他两条到达（i，j）位置的路径，最小路径和dp[i][j]=min(dp[i+1][j+1]，dp[i+1][j])+a[i][j]。i+1，j+1i+1，ji,，jJI60/87dp[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]就是最终的最小路径和。61/87intminPathSum2(vector<vector<int>>&a) //自底向上求最小路径和{ intn=a.size(); intdp[MAXN][MAXN]; for(intj=0;j<n;j++)

dp[n-1][j]=a[n-1][j];

//第n-1行初始化 for(inti=n-2;i>=0;i--) //考虑第0列的边界

dp[i][0]=dp[i+1][0]+a[i][0]; for(inti=n-2;i>=0;i--) //考虑对角线的边界

dp[i][i]=a[i][i]+dp[i+1][i+1]; for(inti=n-2;i>=0;i--) //考虑其他有两条达到的路径 { for(intj=0;j<a[i].size();j++)

dp[i][j]=min(dp[i+1][j+1],dp[i+1][j])+a[i][j]; } returndp[0][0];}62/87自底向上算法空间优化在自底向上算法中阶段i（指求第i行的dp）仅仅与阶段i+1相关，采用降维滚动数组方式，将dp由二维数组改为一维数组。intminPathSum3(vector<vector<int>>&a) //自底向上的优化算法{ intn=a.size(); intdp[MAXN]; //一维动态规划数组

memset(dp,0,sizeof(dp)); for(inti=n-1;i>=0;i--) { for(intj=0;j<a[i].size();j++) //含边界情况的处理

dp[j]=min(dp[j],dp[j+1])+a[i][j]; } returndp[0];}63/878.3.2实战—下降路径最小和（LeetCode931）问题描述：给定一个n×n（1≤n≤100）的整数数组

matrix（元素值位于-100～100），找出并返回通过

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)路径264/87解问题求解—自上而下dp[i][j]表示从第0行开始并且以（i，j）位置为终点的下降路径中最小路径和。采用自上而下的方式求dp。到达（i，j）位置的路径有3条。i-1，ji，ji-1，j-1i-1，j+1min65/87第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]。考虑边界情况如下：①当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行的下降路径中最小路径和。i-1，ji，ji-1，j-1i-1，j+1min66/87class

Solution

{public: int

minFallingPathSum(vector<vector<int>>&

matrix)

{ int

n=matrix.size();

int

ans;

if(n==1)

//n=1为特殊情况，返回第0行的最小元素

{ ans=matrix[0][0];

for(int

j=1;j<n;j++)

if

(matrix[0][j]<ans)

ans=matrix[0][j];

return

ans;

}67/87

intdp[n][n]; memset(dp,0,sizeof(dp));

for(int

j=0;j<n;j++)

//第0行:边界情况

dp[0][j]=matrix[0][j];

for(int

i=1;i<n;i++)

{ for(int

j=0;j<n;j++)

{ if(j==0)

dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];

else

if(j==n-1)

dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+matrix[i][j];

else

dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i][j];

}

}

ans=dp[n-1][0];

//求dp第n-1行中的最小元素ans

for(int

j=1;j<n;j++)

if(dp[n-1][j]<ans)

ans=dp[n-1][j];

return

ans;

}};68/87自上而下算法空间优化由于dp[i]仅仅与dp[i-1]相关，采用滚动数组方法，将dp数组大小改为dp[2][n]，用dp[0][j]存放dp[i-1][j]，用dp[1][j]存放dp[i][j]。class

Solution

{public: int

minFallingPathSum(vector<vector<int>>&

matrix)

{ int

n=matrix.size();

int

ans;

if(n==1)

//n=1为特殊情况，返回第0行的最小元素

{ ans=matrix[0][0];

for(int

j=1;j<n;j++)

if

(matrix[0][j]<ans)

ans=matrix[0][j];

return

ans;

}

int

dp[2][n];

memset(dp,0,sizeof(dp));69/87

for(int

j=0;j<n;j++)

//第0行:边界情况

dp[0][j]=matrix[0][j];

int

c=0;

for(int

i=1;i<n;i++)

{ c=1-c;

for(int

j=0;j<n;j++)

{ if(j==0)

dp[c][j]=min(dp[1-c][j],dp[1-c][j+1])+matrix[i][j];

else

if(j==n-1)

dp[c][j]=min(dp[1-c][j-1],dp[1-c][j])+matrix[i][j];

else

dp[c][j]=min(dp[1-c][j-1],min(dp[1-c][j],dp[1-c][j+1]))+matrix[i][j];

}

}

ans=dp[c][0];

//求dp第n-1行中的最小元素ans

for(int

j=1;j<n;j++)

if(dp[c][j]<ans)

ans=dp[c][j];

return

ans;

}};70/87也可以：1-cc&0c&1自下而上算法空间优化问题求解—自下而上71/87自学(老师讲的太多了)8.4三维动态规划三维动态规划是指设计动态规划算法中采用三维动态规划数组。72/87说明8.4.1Floyd算法设计二维数组B存放当前顶点之间的最短路径长度，其中B[i][j]表示当前顶点i到j的最短路径长度。依顶点编号顺序处理每个顶点，每个顶点的处理看作一个阶段，阶段k（0≤k≤n-1）的结果存放在Bk中，Bk[i][j]表示处理完0～k的顶点后得到的顶点i到j的最短路径长度。73/87阶段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]}74/87intdp[MAXN][MAXN][MAXN];

//三维动态规划数组voidFloyd(vector<vector<int>>&A) //Floyd算法{ intn=A.size(); for(inti=0;i<n;i++) //求B(-1) for(intj=0;j<n;j++)

dp[0][i][j]=A[i][j]; for(intk=1;k<=n;k++) //依次求B(0)到B(n-1) { for(inti=0;i<n;i++) for(intj=0;j<n;j++)

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]}75/87阶段k仅仅与阶段k-1相关，因此可以将dp滚动为dp[2][MAXN][MAXN]。阶段k中求dp[k][i][j]时i和j的任意顺序不影响最后的结果，进一步将dp[2][MAXN][MAXN]滚动为二维数组dp[MAXN][MAXN]intdp[MAXN][MAXN];

//二维动态规划数组voidFloyd(vector<vector<int>>&A) //Floyd算法{ intn=A.size(); for(inti=0;i<n;i++) //求B(-1) for(intj=0;j<n;j++)

dp[i][j]=A[i][j]; for(intk=0;k<n;k++) //依次求B(0)到B(n-1) { for(inti=0;i<n;i++) for(intj=0;j<n;j++)

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

}}76/878.4.2*双机调度问题用两台处理机MA和MB加工n个作业，作业的编号为0～n-1，两台机器均可以加工任何作业。第i个作业单独交给MA时的加工时间是a[i]，单独交给MB时的加工时间是b[i]。现在要求每个作业只能由一台机器加工，但两台机器在任何时刻可以加工两个不同的作业。设计一个动态规划算法，使得两台机器加工完所有n个作业的最短时间（从任何一台机器开工到最后一台机器停工的总时间）。例如，n=6，a

为（2，5，7，10，5，2），b为（3，8，4，11，3，4），结果为15。77/87解用maxA表示MA单独加工所有作业的总时间，maxB表示MB单独加工所有作业的总时间。设置一个三维动态规划数组dp，dp[k][A][B]表示前k个作业（作业编号为0到k-1）在MA用时不超过A且MB用时不超过B时是否有解。阶段k考虑加工作业k-1，分为两种情况：若A-a[k-1]≥0，作业k-1在机器MA上加工，则dp[k][A][B]=dp[k-1][A-a[k-1]][B]。若B-b[k-1]≥0，作业k-1在机器MB上加工，则dp[k][A][B]=dp[k-1][A][B-b[k-1]]。两种情况中任何一种情况求出dp[k][A][B]为true，则dp[k][A][B]为true。78/87dp[0][A][B]=true 0≤A≤maxA，0≤B≤maxBdp[k][A][B]=dp[k-1][A-a[k-1]][B] 当A-a[k-1]≥0，在MA上运行dp[k][A][B]=(dp[k][A][B]||dp[k-1][A][B-b[k-1]]) 当B-b[k-1]≥0，在MB上运行状态转移方程当求出dp后，dp[n][A][B]为true时表示存在一个这样的解，则max(A，B)为这个解对应的总时间。最后答案是在所有解中比较求出总时间最少的时间ans。79/87intn=6; //作业数inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};booldp[MAXN][MAXA][MAXB];

//三维动态规划数组intschedule() //求解算法{ intmaxA=0,maxB=0; for(inti=0;i<n;i++) //求maxA和maxB { maxA+=a[i]; maxB+=b[i]; } memset(dp,0,sizeof(dp)); //初始化为false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++)

dp[0][A][B]=true;

//k=0时一定有解 }80/87 for(intk=1;k<=n;k++) { for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { if(A-a[k-1]>=0) //在MA上加工

dp[k][A][B]=dp[k-1][A-a[k-1]][B]; if(B-b[k-1]>=0) //在MB上加工

dp[k][A][B]=(dp[k][A][B]||dp[k-1][A][B-b[k-1]]); } } }81/87 intans=INF; //存放最少时间 for(intA=0;A<=maxA;A++) //求ans for(intB=0;B<=maxB;B++) if(dp[n][A][B]) ans=min(ans,max(A,B)); returnans;}【算法分析】上述算法的时间复杂度为O(n×maxA×maxB)，空间复杂度为O(n×maxA×maxB)。是多项式级？82/87intn=6; //作业数inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};booldp[2][MAXA][MAXB];

//三维动态规划数组intschedule() //求解算法{ intmaxA=0,maxB=0; for(inti=0;i<n;i++) //求maxA和maxB { maxA+=a[i]; maxB+=b[i]; } memset(dp,0,sizeof(dp)); //初始化为false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { dp[1][A][B]=false;

//k=1时初始化为false

dp[0][A][B]=true;

//k=0时一定有解 } } intc=0;上述算法中dp[k][*][*]仅仅与dp[k-1][*][*]相关，可以将dp改为滚动数组，将第一维MAXN改为2。83/87 for(intk=1;k<=n;k++) { c=1-c; memset(dp[c],false,sizeof(dp[c])); //初始化dp[c]为false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { if(A-a[k-1]>=0) //在MA上加工

dp[c][A][B]=dp[1-c][A-a[k-1]][B]; if(B-b[k-1]>=0) //在MB上加工

dp[c][A][B]=(dp[c][A][B] ||dp[1-c][A][B-b[k-1]]); } } } intans=INF; //存放最少时间 for(intA=0;A<=maxA;A++) //求ans for(intB=0;B<=maxB;B++) if(dp[c][A][B]) ans=min(ans,max(A,B)); returnans;}84/87可以进一步优化空间，设置一维动态规划数组dp，dp[A]表示当MA加工时间为A（0≤A≤maxA）时MB的最少加工时间。首先将dp的所有元素初始化为0。阶段k：考虑加工作业k-1，分为两种情况：当A<a[k-1]时，只能在MB上加工，MA的加工时间仍然为A，MB的加工时间为dp[A]+b[k-1]，则dp[A]=dp[A]+b[k-1]。当A≥a[k-1]时，作业k-1既可以由MA加工也可以由MB加工。由MA加工时，MA的加工时间变为A-a[k-1]；由MB加工时，MB的加工时间为dp[A]+b[k-1]。取两者中的最小值，则dp[A]=min(dp[A-a[k-1]]，dp[A]+b[k-1])。当求出dp后，max(A，dp[A])为完成n个作业的一个解，问题的最后答案是在所有解中比较求出总时间最少的时间ans即可。85/87intn=6; //作业数inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};intschedule() //求解算法{ intmaxA=0; for(inti=0;i<n;i++) //求maxA maxA+=a[i];

intdp[MAXA];

//一维动态规划数组 memset(dp,0,sizeof(dp)); //初始化为086/87 for(intk=1;k<=n;k++) { for(intA=maxA;A>=0;A--) { if(A<a[k-1]) //此时只能在MB上运行

dp[A]=dp[A]+b[k-1]; else //否则取MA或者MB上处理的最少时间

dp[A]=min(dp[A-a[k-1]],dp[A]+b[k-1]); } } intans=INF; //存放最少时间 for(intA=0;A<=maxA;A++) ans=min(ans,max(A,dp[A])); returnans;}【算法分析】算法时间复杂度为O(n×maxA)，空间复杂度为O(maxA)。87/8788/87思政案例第8章动态规划8.1动态规划概述8.2一维动态规划CONTENTS提纲8.3二维动态规划8.4三维动态规划8.5字符串动态规划8.6背包动态规划8.7树形动态规划8.8区间动态规划89/648.5字符串动态规划字符串动态规划是指采用动态规划算法求解字符串的相关问题。说明90/648.5.1最长公共子序列问题一个字符串的子序列是指从该字符串中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。给定两个字符串a和b，称字符串c是a和b的公共子序列，是指c同是a和b的子序列。该问题是求两个字符串a和b的最长公共子序列（LCS）。91/64设计二维动态规划数组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]=m