牛X动态规划入门篇

1、动态规划入门篇ACM暑期集训2009/08/12前言纵观ACM届，大到每年的全球总决赛，小到TC的SRM抑或各个OJ的月赛，我们很轻易的发现一个共同的规律动态规划在其中稳稳的占据了一个重要的地位。可以说，掌握了动态规划，不一定会成为大牛，但是一只大牛，是肯定精通动态规划的。动态规划，和分治法一样，是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归求解各子问题，然后合并子问题的解而得到原问题的解。于此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重

2、新计算答案。动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优解的值。总结：自从有了动态规划，这个世界变得好美妙！目录0.动态规划的基本步骤1.一个例题2.什么时候需要动态规划3.最优子结构4.重叠子问题5.动态规划的两个重要元素状态&状态转移方程6.备忘录介绍7.例题 数字三角形花束摆放 最大数字子串积木游戏 Subsquence 炮兵阵地(状态压缩动态规划)8.练习 : NOJ 江苏省赛回放 C D E（三角形演变题） H 0.动态

3、规划的基本步骤1）描述最优解的结构2）递归定义最优解的值3）按自底向上的方式计算最优解的值4）由计算出的结果构造一个最优解第1-3步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步，则有时要在第三步的计算中记录一些附加信息，使构造一个最优解变得容易。1.一个例题例一：装配线调度问题描述：某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1n ），两个装配线对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为Aij。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个

4、流水线的下一个装配站则需要一定的时间Tij。汽车进入流水线不需要花时间，出流水线时需要花时间Tin。汽车的装配需要按顺序经过所有装配站。现在已知装配时间Aij 和转移时间Tij，要求输出装配一辆汽车所需要的最短时间。 方案一：暴力搜索，穷举所有装配可能，然后选择极小。显然这个方案是不可行的，因为我们分析可知，装配方式共有2N种（将所使用装配站一内的站看做一个集合，全集是1.N，子集就有2N），这时时间复杂度到达O（2N），显然N太大的时候是一定会TE的。方案二：动态规划。步骤一：描述最优解的结构在这里就是通过工厂最快路线的结构其实这里就是描述问题是否具有一个最优子结构，即可以利用子问题的最优解

5、构造原问题的一个最优解。在这道题中，观察一条通过S1，j的最快路线，我们发现，它必然是通过S1，j-1或S2，j-1中的一个的最快路线（如果不是最快，则自我矛盾，S1，j就不是最快了）为了解决这个问题，即寻找通过人一条装配线上的装配站J的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站J-1的最快路线。所以，对于这个问题，我们可以求子问题的最优解，从而得到原问题的最优解。PS：状态，状态转移方程的概念将会在理脱出，后面会提到，只要找好了状态方程（加元等手段），就能轻松使用动态规划。步骤二：一个递归的解利用子问题的最优解来递归定义一个最优解的值。在这个问题中，我们选择在两条装备线上通

6、过装配站j的最快路线的问题作为子问题（j=1，2，3.，n）。令fij表示一个底盘从起点到装配站Si，j的最快可能时间。我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记做f*。f* = min(f1n + x1,f2n + x2)下面的问题就是确定f11和f21显然，不管是从那条线路开始装配的，底盘肯定是直接到达装配站1的，也就是说之前是不用计算转移到装配站1的时间的。则f11 = e1 + a1,1 f21 = e2 + a2,1现在计算fij，显然简单递推可知：fi1 = ei + ai,1;fij = min(fij-1 + ai,j , fij-1 + ti,j-1 + a2,

7、j)fij的值就是子问题的最优解的值。注意：这里，我们不需要知道最优解到底是什么，我们只需要求出最优解是多少即可，所以对构造过程可以不进行跟踪。现在，写出一个递归算法计算通过工厂的最快路线是一件很简单的事情了。只需基于以下几个公式即可：f* = min(f1n + x1,f2n + x2)fi1 = ei + ai,1;fij = min(fij-1 + ai,j , fij-1 + ti,j-1 + a2,j)现在我们来看这种算法的时间复杂度，发现它有一个问题:它的执行时间是关于n的指数形式即O（2n），这是一个时间复杂度很高的算法。我们来考虑是否能进一步提高它的效率。现在考虑这样一种方式F

8、ASTEST-WAY(a , t , e , x , n)f11 = e1+a1,1f21 = e2 + a2,1 /这两行计算f11和f21的值For j=2 to n /这个循环用来计算fij的值 do if f1j-1+a1,j=f2j-1+t2,j-1+a1,j then f1j = f1j-1+a1,j else f1j=f2j-1+t2,j-1+a2,j if f2j-1+a2,j=f1j-1+t1,j-1+a2,j then f2j = f2j-1+a2,jif f1n+x1= 0; -i ) /从最下层开始，计算每个x，y位 /置的元素到 最后一行的最小值for ( j = 0

9、; j = i; +j ) /计算每一行的每一个数字tmp = soui + 1j;if ( soui + 1j + 1 tmp ) /*j在变化，j每循环完次都得到一个这一行到最底行最小的位置，同时也记录了每个位置到最底行的值；这里的if是在找每个位置的下两步路线中较小的一个*/tmp = soui + 1j + 1;souij += tmp;printf( %dn, sou00 );35例题二：花束摆放问题描述 现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(FV)。花束可以移动，并且每束花用1至F的整数

10、唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。372解题思路 状态表示法一： 设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(这里ki)，前i种花束能够获得的最大美学

11、值(之和)。这样，原问题的最优值可以通过计算maxS(F,k)FkV获得。 下面要分析一下这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。 38 最优子结构性质：对满足FkV的k，设T(F,k)是达到最优值S(F,k)的一种最佳摆放方式，其中，第F-1种花束摆在第j个花瓶中(j1每走一步，计算出了所有i的花束摆放在所有可能的位置之后的所有值。最后，递推出了s(F,*)的值取最大既得到结果。S(1,k)=A(1,k)第i-1个花摆在那里之后，下一步怎么摆，只跟现在花在哪里有关，而与前面的摆放顺序无关，无后效性。大家用心想一下，问题其实还是像装配线一样，被分解成了有限个分支的最大值

12、问题。切记，使用DP的时候，眼光不要一直盯着最后的最优，一步一步看，只要你现在最优，并且无后效性，就可以DP下去。39 在计算S(i,k-1)时，已经计算出了S(i-1,j)，i-1jk-2及其 maxS(i-1,j)i-1jk-2 。因此，计算S(i,k)时，只要将S(i-1,k-1)与max S(i-1,j)i-1jk-2 进行比较即可求得,即子问题重叠性质。这样做可以大大减少计算量。即不用每次都去全部比较，求最大值。 事实上，还可以有更直接的方法。 状态表示法二： 设Si,k表示第i种花束摆在第k个之前(包括第k个)的任意某个花瓶中，前i种花束能够获得的最大美学值(之和)。这样，原问题的

13、最优值即为SF,V。这比前一个表示法更直接。 40 容易验证，计算SF,V的问题具有最优子结构性质。 其递归方程为： Si,k=maxSi-1,k-1+A(i,k)，Si,k-1，(i1，ki); /很精妙，注意理解 初始条件为：S1,1=A1,1; S1,k=maxA(1,k),S1,k-1，(k1);Si,i=Si-1,i-1+A(i,i)， (i1) 41算法设计(状态表示法二) 算法的过程如下： s00 = a00; out00 = true;for ( j = 1; j a0j ? s0j - 1 :a0j;out0j = ( s0j != s0j - 1 );for ( i = 1

14、; i f & i ?= si - 1j - 1 + aij;outij = ( sij != sij - 1 );42sij = si - 1j - 1 + aij; outij = true;if ( i ?= sij - 1; outij = ( sij != sij - 1 );43例题三：最大数字子串NKOJ 1760 最大数字子串:问题描述：输入n(1=n0，如果后边是正数的话，完全可以加上这3个数（比如后边的5）-1 2 8 5 10 ？相同处理： -1 2 8 5 10 3 17 12？后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此处应该断开了！记录-15！

15、最后-1 2 8 5 10 3 17 12 -15 1 9 5 1447！还有一点，如果输入全为非正数的话，那么最大子串就是最大的那个数了！48伪代码：输入数组ai,用数组si记录当前最大子串和,num记录最大值。for(i=0;in;i+) 输入ai; s0=a0; num记录当前最大的数； if(num=0) 最大就为num!for(i=1;in;i+)if(si-1 0 | (si-1 + ai) = 0) si = ai;elsesi = si-1 + ai;num = (num si) ? si:num;/*条件运算符 （numbi true则bi,false则num）*/49例题四

16、：积木游戏LRJ的书，P119。这道题和我们程序设计大赛的时候的第四题（是不是第四？记不清了。）猩猩吃香蕉那题有异曲同工之妙。大家明白这题之后可以回忆一下我们的比赛。例题五： Subsequence 给定一个数串和一个数S，在数串中找出大于等于S的一个连续子列！且该子列是满足上述条件的最短子列！数串数字个数N：10N100000,每个数小于10000。比如： 10 15 5 1 3 5 10 7 4 9 2 8 最短为2； 5 11 1 2 3 4 5 最短为3。该题简单分析：题意知所有数全为正数 A sequence of N positive integers (10 N 100 000)

17、，每新增一个数，若前面的数不足S,加上此数，然后与S比较！小于S可不管！52大于S：假设此时新增项ai,设当前和为sumi,用另一数组记录当前长度位置长度lengthi。那么现在在构成sumi的数的最前端i-lengthi+1处，有可能出现多余的项，哪怕删除它们也满足剩下的数的和sumi(长度已更改为新的lengthi! )逐项除之即可！lengthi记录的是到达每个位置的时候，这个串现在有多长。53寻找最短子列：Length全为0,没有最短子列!否则为大于0的最小值。if(b1n-1=0) num=0;else num=n; for(i=0;i0) num=(b1inum)?b1i:num;

18、 54例题六：炮兵阵地POJ 1185经典的DP问题题意描述：司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支