信息学奥赛NOI动态规划入门(C++)培训讲学课件.ppt

1、动态规划入门动态规划入门 上课内容上课内容什么是动态规划基本概念斐波那契数列经典的类型最短路径问题最短路径问题-求求A A到到E E的最短路的长度的最短路的长度穷举？贪心？搜索？思考： 仔细观察本图路径的特殊性，可以分成4个阶段：第一阶段：A经过A-B1或A-B2到B第二阶段：B1有三条路通；B2有两条通路阶段阶段1阶段阶段2阶段阶段3阶段阶段4思考：倒着推；设F(x)表示x到E的最短路径的长度阶段4：F(D1)=3;F(D2)=4;F(D3)=3阶段3：F(C1)=minF(D1)+C1到D1的路径长度， F(D2)+C1到D2的路径长度 F(C2)阶段阶段1阶段阶段2阶段阶段3阶段阶段4我

2、们把F(x) 称为当前x的状态； 在这个例子中每个阶段的选择依赖当前的状态，又随即引起状态的转移，一个决策序列(E D3-C4-B2-A)就是在变化的状态中产生的，故有“动态”的含义。阶段阶段1阶段阶段2阶段阶段3阶段阶段4int fib(int n)int fib(int n) if ( n = 1 | n=2 ) return 1; if ( n = 1 | n=2 ) return 1; else return fib(n-1) + fib(n-2); else return fib(n-1) + fib(n-2); 时间复杂度？能优化吗？例例1: 1: 斐波那契（斐波那契（Fibona

3、cciFibonacci）数列）数列斐波纳契数列斐波纳契数列大量重复计算！大量重复计算！ 如何可以使计算仅需一如何可以使计算仅需一次？次？例例1: 1: 斐波那契（斐波那契（FibonacciFibonacci）数列）数列/dp数组，用以保存已经计算过的结果/dpn记录F(n)的结果，dpn= -1表示没有计算过int fib(int n)int fib(int n) if ( n = 1 | n=2 ) return 1; if ( n = 1 | n=2 ) return 1; if ( dpn != -1 ) return dpn; if ( dpn != -1 ) return dpn

4、; else else dpn = fib(n-1) + fib(n-2); dpn = fib(n-1) + fib(n-2); return dpn; return dpn; 时间复杂度？基本概念基本概念阶段： 问题的过程被分成若干相互联系的部分，我们成为阶段，以便按一定的次序求解。状态： 某一阶段的出发位置称为状态，通常一个阶段包含若干状态。决策： 对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发，通过一次选择性的行动移至下一个阶段的相应状态。 例例2: 数字三角形一个由非负数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有个数，从第一行的数开

5、始，每次可以选择向左下或是向右下走一格，一直走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？。数字三角形格子编号穷举？贪心？搜索？穷举？贪心？搜索？数组存储深搜（递归实现）程序清单：void f( int i, int j );void f( int i, int j ); s=s+a i j ; s=s+a i j ; if ( i=4 ) if ( i=4 ) if ( s max ) max = s; if ( s max ) max = s; else else f( i+1, j )f( i+1, j ); ; s=s-a i+1 j ; s=s-a i+1 j ;

6、 f( i+1, j+1)f( i+1, j+1); ; s=s-a i+1 j+1; s=s-a i+1 j+1; 格子编号分析：考察设以格子(i,j)为首的“子三角形”的最大和为di,j（我们将不加区别的把这个子问题(subproblem) 本身也称为di,j），则原问题的解是d1,1我们关心的是从某处出发到底部的最大和： 从(2,1)点出发的最大和记做d2,1; 从(2,2)点出发的最大和记做d2,2; 从（1，1）出发有两种选择（2，1）或（2，2）在已知d2,1和d2,2的情况下，应选择较大的一个。思考：考虑更一般的情况，当前位置（i，j）看成一个状态， 定义状态（i，j）的指标函数

7、d(i，j) 为从格子（i，j）出发时能得到的最大和（包含格子（i，j）本身的值）。 原题的解：？d（？，？）格子编号d1，1 思考：观察不同状态如何转移的。 从格子（i，j）出发有两种决策。 如果（i，j）格子里的值为a (i ，j) 向左走需要求“从（i+1，j）出发的最大和”，就是di+1，j。 向右走需要求“从（i+1，j+1）出发的最大和”，就是di+1，j+1。 如何选呢？ 思考：边界条件？其中较大的一个，再加上a(i,j)的值就是di,j。di,j=ai,j+maxdi+1,j,di+1,j+1思想：思想：从上向下思考，从底向上计算从上向下思考，从底向上计算数字三角形813211

8、62324时间复杂度时间复杂度O O（n n2 2） 在计算在计算dij前，前，di+1j,di+1j+1已计算好已计算好了！了！ 方法1：递推计算void void solvesolve () () intint i , j; i , j;for(j = 1; j = n; j +) dnj = anj;for(j = 1; j = 1; i - -)for(i = n -1; i = 1; i - -)for(j = 1; j = i; j +)for(j = 1; j = 0) return if(d i j = 0) return dij;dij;dij dij = aij+max(s

9、olve ( i+1, j ), solve ( i+1 , j +1) );= aij+max(solve ( i+1, j ), solve ( i+1 , j +1) );returnreturn dij; dij; 时间复杂度时间复杂度O（n2） 不必事先确定各状态的计算顺序不必事先确定各状态的计算顺序方法3：记忆化搜索动态规划基本思想 建立子问题的描述，建立状态间的转移关系，使用递推或记忆化搜索法来实现。状态定义用问题的某些特征参数描述一个子问题。在本题中用di,j表示以格子(i,j)为根的子三角形的最大和。在很多时候，状态描述的细微差别将引起算法的不同。状态转移方程即状态值之间的递

10、推关系。这个方程通常需要考虑两个部分：一是递推的顺序，二是递归边界（也是递推起点）。从直接递归和后两种方法的比较可以看出：重叠子问题(overlapping subprob-lems) 是动态规划展示威力的关键。考察：d(1,1)；d(2,1)；d(2,2)这些问题的共性：都是求从一个位置出发到底部的最大值；是一个共同的问题。d(2,1)d(2,1)d(2,2)d(2,2)重叠子问题考察：d(1,1)；d(2,1)；d(2,2）；可以发现每个子问题结果都是最优的。d(2,1)d(2,1)d(2,2)d(2,2)最优子结构什么是动态规划？什么是动态规划？动态规划是求解包含重叠子问题的最优化方法

11、动态规划的性质？ 子问题重叠性质：在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。 最优化子结构性质：若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。 能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的 无后效性：即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。数

12、字三角形 如果数字三角形(有负数)求的是从上到下的和最接近零。就不符合无后效性原则。动态规划的优势动态规划的优势1.动态规划比穷举具有较少的计算次数 从数塔问题可以看出，层数为k时， 穷举算法求路径的条数2k-1 动态规划计算的次数为: 穷举最多计算到n=20，动态规划可以算到n=1002.递归需要很大的栈空间，而动规的递推法不需要栈空间；使用记忆化搜索比较容易书写程序。2) 1( kk思考： 还有一种思考方法，从下 向上考虑，观察不同状态如何转 移的。从格子（i，j）出发有两 种决策。 思考：边界情况：？思考：最后的结果：？d11=a11di1=di-11+ai1 第1列dii=di-1i-

13、1+aii 对角线maxdn1,dn2dnnd(i,j)为：取d(i-1,j) 和d(i-1,j-1)中较大的一个加上a(i,j)的和。这种方法本这种方法本质就是递推质就是递推例例3:3:最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum） 给定k个整数的序列A1,A2,.,Ak ，其任意连续子序列可表示为 Ai, Ai+1, .,Aj ，其中 1 = i = j = k。最大连续子序列是所有连续子序中元素和最大的一个。 例如给定序列 -2, 11, -4, 13, -5,

14、-2 ，其最大连续子序列为11,-4,13，最大连续子序列和即为20。 暴力枚举？时间复杂度为？能优化吗？复杂度？暴力枚举？时间复杂度为？能优化吗？复杂度？令状态dpi表示以Ai作为末尾的连续序列的最大和（Ai必须作为序列的末尾）。以样例为例，序列 -2, 11, -4, 13, -5, -2 ，下标分别设为：0，1，2，3，4，5；dp0dp1dp2dp3dp4dp5问题转换为dp0,dp1,dpn-1中的最大者。最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum） dpi

15、表示以Ai作为末尾的连续序列的最大和（Ai必须作为序列的末尾）;只有两种情况：1、这个最大和的连续序列只有一个元素，即以Ai开始，以Ai结尾；最大和就是最大和就是AiAi本身本身。2、这个最大和的连续序列有多个元素，从前面某处Ap开始（pi)；一直到Ai结尾。也就是 dpi-1+Aidpi-1+Ai; Ap+Ap+Ai-1+Ai=dpi-1+Ai;+Ai-1+Ai=dpi-1+Ai;最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum） 转移方程： dpi= max Ai ,

16、dpi-1 + Ai dpi= max Ai , dpi-1 + Ai 边界：边界：dp0=A0dp0=A0最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum） n代码：代码： dp0 = A0;dp0 = A0; for (int i=1 ; i n ; i+) for (int i=1 ; i n ; i+) dpi= max ( Ai , dpi-1 + Ai ) dpi= max ( Ai , dpi-1 + Ai ) 结果？结果？动态规划的核心动态规划的核心设计状态

17、 和状态转移方程最长上升子序列（最长上升子序列（LISLIS）NOI 1759NOI 1759 最长上升子序列（最长上升子序列（LISLIS）NOI 1759NOI 1759样例输入：样例输入：71 7 3 5 9 4 8样例输出：样例输出：4上升子序列：上升子序列：1, 73, 4, 8最长上升子序列：最长上升子序列：1, 3, 5, 91, 3, 5, 81 2 3 4 5 6 7a 1 7 3 5 9 4 8如何划分阶段？如何划分阶段？以从左向右数的个数为阶以从左向右数的个数为阶段。段。状态如何描述？状态如何描述？状态描述及转移状态描述及转移 1 2 3 4 5 6 7a 1 7 3 5

18、 9 4 81 112 2 1 73 3 1 7 34 4 1 7 3 55 5 1 7 3 5 96 6 1 7 3 5 9 47 7 1 7 3 5 9 4 8f1223444阶阶段段状态描述及转移状态描述及转移 1 2 3 4 5 6 7a1 7 3 5 9 4 8f1 2 2 3 4 3 41 2 3 4 5 6 7a 1 7 3 5 9 4 81 112 2 1 73 3 1 7 34 4 1 7 3 55 5 1 7 3 5 96 6 1 7 3 5 9 47 7 1 7 3 5 9 4 8f1223434阶阶段段求解步骤求解步骤解题顺序解题顺序内容内容划分阶段划分阶段状态描述状态

19、描述转移方程转移方程边界条件边界条件答案答案以从左向右数的个数为阶段。以从左向右数的个数为阶段。核心代码核心代码a0 = -1; f0 = -1; / 边界for (int i = 1; i = n; i+) / 枚举阶段 for (int j = 0; j i; j+) / 枚举可能的决策 if(aj ai) fi = max(fi, fj + 1); int ans = 0;for (int i = 1; i = n; + i) ans = max(ans, fi);时间复杂度：O(n2)思考：如何求一个最长上升子序列？给定两个字符串（或数字序列）A和B（长度分别为n和m），求一个字符串，

20、使得这个字符串是A和B的最长公共部分（子序列可以不连续）。如上图，字符串“sadstory”与“adminsorry”的最长公共子序列为“adsory”，长度为6。 暴力枚举？时间复杂度为？时间复杂度？暴力枚举？时间复杂度为？时间复杂度？例例5 5：最长公共子序列：最长公共子序列（Longest Common SubsequenceLongest Common Subsequence，LCSLCS）状态定义：令dpij表示字符串A的i号位和字符串B的j号位之前的LCS长度（下标从1开始）。如：dp45表示“sads”与“admin”的LCS长度。转移方程：两种情况：1.Ai = Bj, 试分析

21、 dp462.Ai != Bj, 试分析dp33试试看？你能写出转移方程吗？例例5 5：最长公共子序列：最长公共子序列（Longest Common SubsequenceLongest Common Subsequence，LCSLCS）状态定义：令dpij表示字符串A的i号位和字符串B的j号位之前的LCS长度（下标从1开始）。如：dp45表示“sads”与“admin”的LCS长度。转移方程：两种情况：dpij= dpij= dpi-1j-1+1, Ai=Bjdpi-1j-1+1, Ai=Bj max(dpi-1j , dpij-1) , Ai!=Bj max(dpi-1j , dpij-

22、1) , Ai!=Bj 边界？边界？例例5 5：最长公共子序列：最长公共子序列（Longest Common SubsequenceLongest Common Subsequence，LCSLCS）dpi0=dp0j=0 dpi0=dp0j=0 （0=i=n,0=j=m0=i=n,0=j=m）int lenA=strlen(A+1);int lenA=strlen(A+1);int lenB=strlen(B+1);int lenB=strlen(B+1);/ /核心代码：核心代码： for(int i=1; i = lenA; i+) for(int i=1; i = lenA; i+)

23、for (int j=1; j lenB; j+) for (int j=1; j lenB; j+) if (Ai = Bj) if (Ai = Bj) dpij = dpi-1j-1+1; dpij = dpi-1j-1+1; else else dpij = max ( dpi-1j , dpij-1 ) dpij = max ( dpi-1j , dpij-1 )答案：？答案：？ 例例5 5：最长公共子序列：最长公共子序列（Longest Common SubsequenceLongest Common Subsequence，LCSLCS）动态规划入门（下）动态规划入门（下） 骑士游

24、历问题骑士游历问题 设有n*m的棋盘（2=n，m=50)；在棋盘上任意一点有一个中国象棋的马，同时给出起点P和终点Q，求所有从起点出发到终点的路径数目。（马跳跃有四个方向） 设d(i,j)为从(i,j)位置出发到Q点的路径条数。i为行号，j为列号。考察任意一个位置（i，j）d(i-2,j+1)d(i-1,j+2)d(i+1,j+2)d(i+2,j+1)d(i,j)=？边界条件？d(i,j)=d(i-2,j+1)+d(i-1,j+2)+d(i+1,j+2)+d(i+2,j+1)边界条件为越界时d(i,j)=0，d(Q)=1最低通行费（最低通行费（NOI 7614NOI 7614）试题描述：（试题

25、描述：（1s,64M）一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。最低通行费（最低通行费（NOI 7614NOI 7614）输入要求：输入要求：第一行是一个整数，表示正方形的宽度N (1 = N 100)；后面 N 行，每行 N 个不大于 100 的整数，为网

26、格上每个小方格的费用。输出要求：输出要求：至少需要的费用。最低通行费最低通行费样例输入：样例输入：51 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33 样例输出样例输出:10914681025715 1768918 2010 11 12 19 2120 23 25 29 33109=1+2+5+7+9+12+19+21+33因为必须在因为必须在(2N-1)个单位时间穿越出去，所以个单位时间穿越出去，所以只能向只能向右或者向下走右或者向下走。最低通行费最低通行费 (i-1,j)(i,j-1)(i,j)表格化表格化从左到

27、右，从上到下，注意边界！1468102571517689182010111219212023252933infInfinfinfinfinfinf1 15 5111119192929inf3 38 8151530304646inf9 91616242442426262inf19192727363655557676inf3939505051518080109109列列行行 核心代码核心代码memset(f,0 x3f,sizeof（f）);f11 = a11;for (int i=1;i=n;i+) for (int j=1;j=n;j+) if (i=1 & j=1) continue; fi

28、j = min(fi-1j,fij-1)+aij; cout fnn n时 ，d(i,j)=0,j=1; i-)for ( int i = n ; i =1; i-) for (int j = 0; j = c; j+) for (int j = 0; j = vi) if (j = vi) fij =max(dij,di+1j-vi+wi); fij =max(dij,di+1j-vi+wi); d d(i,j)=maxd(i+1,j),d(i+1,j-vi)+Wi(i,j)=maxd(i+1,j),d(i+1,j-vi)+Wi状态的确定状态的确定2对称的思考：我们用f f (i,j)表示把

29、前i个物品装到体积是j的背包中的最大总重量。 则有 f f (i,j)=max (i,j)=max f f (i (i- -1,j),1,j), f f (i (i- -1,j-vi)+Wi1,j-vi)+Wi边界是i=0时为0,j0时为负无穷。答案是f f (n,c)代码代码for ( int i = 1 ; i =n; i+)for ( int i = 1 ; i =n; i+) for (int j = 0; j = c ; j+) for (int j = 0; j = vi) if (j = vi) fij =max(fij,fi-1j-vi+wi); fij =max(fij,fi

30、-1j-vi+wi); f f (i,j)=max (i,j)=max f f (i (i- -1,j),1,j), f f (i (i- -1,j-vi)+Wi1,j-vi)+Wi物品无限背包问题物品无限背包问题有n种物品，每种均无限多。第i种物品的体积为Vi，重量为Wi。选一些物品装到一个容量为C的背包中，使得背包内物品在总体积不超过C的前途下重量尽量大。似曾相识？d(i)表示从结点i到结点0的路径的边权之和最大；d(i)=maxd（i-Vj）+Wi (1=j=Vj)问题求：d（C） 所求问题转换为：以C为起点（终点任意）的、边权之和的最大的路径。总 结1、递推的边界条件一般很明显，而动态

31、规划的边界条件比较隐蔽，容易被忽视；2、递推的数学性一般较强，而动态规划的数学性相对较弱；3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；4、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。 动态规划和一般递推的不同点？动态规划和一般递推的相同点？无后效性和有边界条件。算法模式图算法模式图当前阶段i多个规划规划(决策)当前最优决策当前非最优决策i向着目标阶段不断改变(动态动态)规划方向目标阶段初始阶段求得的一个最优解求得的一个最优解当前阶段的决策仅受前一阶段决策的影响,并决定下一个阶段的决策动态规划动态规划友情提醒：动态规划是一种用途很广的问题求解方法，它本身并不是一个特定的算法，而是一种思想，一种手段。 动态规划的核心是状态和状态转移的方程。 用递推法计算状态转移方程的关键是边界和计算顺序。多数情况下递推的时间复杂度是：状态总数每个状态的决策个数决策的时间。 可以使用记忆化搜索的方法计算转移方程。当采用记忆化搜索时，不必事先确定各状态的计算顺序，但需要记录每个状态“是否已计算过”。