搜索
ACM程序设计第十四-十五讲-动态规划湖南工学院张新玉zhangxinyu247@163.com目录•什么是动态规划•状态阶段决策•一种确立状态的方法•两种简单的DP武器•三种特殊的动态规划什么是动态规划•在学习动态规划之前你一定学过搜索.那么搜索与动态规划有什么关系呢?我们来下面的一个例子.数字三角形•给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形•无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}•对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。•解决方法：记忆化搜索•我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程:•f1:=f(i-1,j+1);f2:=f(i-1,j);•iff1f2thenf:=f1+a[i,j]elsef:=f2+a[i,j];•显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：记忆化搜索•Opt[i,j]-每产生一个f(i,j)，将f(i,j)的值放入opt中，以后再次调用到f(i,j)的时候，直接从opt[i,j]来取就可以了。•于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.记忆化的功效动态规划的实质•可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子问题的原因.记忆化,正符合了这个要求.状态阶段决策•或许有一种对动态规划的简单称法,叫分阶段决策.其实我认为这个称法并不是很能让人理解.那么下面我们来看看阶段,状态,决策这三者间得关系吧.状态阶段决策•状态是表现出动态规划核心思想的一个东西.而分阶段决策这个东西有似乎没有提到状态,这是不科学的.•阶段,有些题目并不一定表现出一定的阶段性.数字三角形的阶段就是每一层.这里我们引入一个概念---以前状态.但阶段不是以前状态,状态是阶段的表现形式.数字三角形的以前状态就是当前层的前一层.•那什么是决策呢?我们看看下面一张图就知道了.显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。动规的要诀－状态•我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。•我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。拦截导弹•拦截导弹（Noip2002）•某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。拦截导弹•状态的表示－f[i]，表示当第i个导弹必须选择时，前i个导弹最多能拦截多少。•每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个打的导弹。以前状态就是在这个导弹以前打的那个导弹。•显然这是十分能够体现状态间的联系的题目。最长公共子串•给出两个字符串序列。求出这样的一个最长的公共子串：子串中的每个字符都能在两个原串中找到，而且每个字符的顺序和原串中的顺序一致。交错匹配•交错匹配（最长公共子串的改编）给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错,交错的连线不能再和别的交错连线有交点.问这两排数字最多能形成多少个交错匹配.1233241513510312324121553状态的表示－f[i,j]表示前i个第一排的数字和前j个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错的后面两个位置.例如上图中当前状态是3和1(第一组交错),枚举他的以前状态就有13.这样在13之前会有一个最优值存在,因此可以由此得到31的最优值.买车票•买车票(Ural1031)Ekaterinburg城到Sverdlovsk城有直线形的铁路线。两城之间还有其他一些停靠站,总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1，Sverdlovsk城编号为N。买车票某两站之间车票价格由这两站的距离X决定.当0X=L1时，票价为C1元.当L1X=L2时，票价为C2元.当L2X=L3时，票价为C3元.当两站距离大于L3时没有直达票，所以有时候要买几次票做几次车才行。比如，在上面的例图中，2-6没有直达票，有几种买票方法可以从2-6，其中一种是买C2元的2-3车票，再买C3元的3-6车票。买车票给定起点站和终点站还有L1,L2,L3,C1,C2,C3，求出要从起点到终点最少要花多少钱.怎么办买车票当前所在的某个车站这一题的以前状态其实只有3种.即满足3种距离(收费)情况的3个车站.要知道这3个车站可以先做一个预处理.显然这3个车站在满足距离限制的条件下应该越远越好.买车票•预处理很容易想出一个N^2的预处理,但是那样是会超时的.由于尽量要让车站离得远(费用是一样的啊)因此在每种收费情况下,每个车站的以前状态车站一定是递增的序列.这里是只要O(N)的程序:forj:=1to3dobegink:=en-1;fori:=endowntobedobeginwhile(way[i]-way[k]=l[j])and(k=be)dodec(k);p[i][j]:=k+1;end;end;数组P[i][j]表示的是I状态的第j种以前状态.买车票动态规划的部分fori:=be+1toendo{枚举当前状态}begincost[i]:=maxlongint;forj:=1to3do{枚举以前状态}beginif(p[i][j]i)and(cost[i]cost[p[i][j]]+c[j])thencost[i]:=cost[p[i][j]]+c[j];end;end;动规的要诀－状态•有时候当前状态确定后,以前状态就已经确定,则无需枚举.Tom的烦恼•Tom是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂，专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。Tom当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，Tom不知如何进行取舍。Tom的烦恼•Tom的烦恼按结束时间排序，枚举结束时间作为当前状态,以前状态就是该结束时间对应的起始时间，这是已经确定的.文字游戏•文字游戏(fairfox邀请赛1)给你一份单词表，和一个句子。求出该句子能有多少中不同的划分方法.例如:单词是abcdabcd句子是abcd他共有4种完全划分方案:ab/cda/b/c/da/b/cdab/c/d;当前状态就是单词在句子中向后靠的位置,以前状态就是确定这个单词位置以后,除掉这个单词长度后的一个位置.状态转移方程是:F[i]:=F[i]+F[i-length(word[j])]IOI中有一题《前缀》也是类似的题目.决策中的定量•状态转移方程的构造无疑是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量.定量处理的过程也就是决策实施的过程.寻找定量•最佳加法表达式•有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中.使得所形成的算术表达式的值最小.或许你不明白我在说什么,那么我们通过题目来说明吧最佳加法表达式•这一题中的定量是什么呢?因为是添入加号,那么添完加号后,表达式的最后一定是个数字串,这就是定量.从这里入手,不难发现可以把以前状态认为是在前i个字符中插入k-1个加号(这里的i是当作决策在枚举),然后i+1到最后一位一定是整个没有被分割的数字串,第k个加号就添在i与i+1个数字之间.这样就构造出了整个数字串的最优解.而至于前i个字符中插入k-1个加号,这又回到了原问题的形式,也就是回到了以前状态,所以状态转移方程就能很快的构造出来了.最佳加法表达式•用f[i,j],表示的是在前i个字符中插入j个加号能达到的最小值,最后的答案也就是F[length(s),m].•于是就有一个动规的方程:F[i,j]:=min(f[i,j],f[k,j-1]+num[k+1,i])num[k+1,i]表示k+1位到i位所形成的数字.这里显然是把加号插入了第k+1个位置上.•知道了这一题怎么做以后,乘积最大的一题也是完全一样的形式,谁还会去用搜索?定量•现在大概大家已经了解了定量是什么,那么我们下面通过几道题目来了解一下定量的威力.游戏•游戏(Noip2003普及组)•这一题的描述简单说一下:在一个圈的周围有n个石子,将他们划分成m堆(每堆中的石子必须连续相邻),每一堆石子计算出他们的总重量mod10的值,然后将这些值相乘,求得到的结果最大最小值是多少.游戏•这一题作者其实是根据最佳加法表达式改编的.但是他加了一个在圈上的条件,怎么办呢?寻找定量!游戏•可想而知,因为至少要分成1堆,那么至少有两个石子之间是会被分隔开的.这就是定量!当划分数1时,一定有两个相邻石子被划分到不同的堆里去!•于是这个圈被这样的理解断成了一条线,解法就和最佳加法表达式一样了.•当然这个断开的位置是需要枚举的,然后保留下一个最优值.显然这个断开的操作对整个过程没有影响,因为这是必然的情况,这是定量!最优三角形划分•问题描述•给定一具有N（N50）个顶点(从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？最优三角形划分•这一题大概搜都是十分麻烦的,可是这一题Dp的话,比搜索要容易实现和容易理解得多.•先得表示一下状态,我们用f[i,j]表示以第i个点开头,顺时针长度为j的一块子多边形.如上图中f[1,5]表示的子多边形(黑色虚线划开)最优三角形划分•如果没有红色虚线的部分,或许你会认为决策应该是枚举子多边形内的两点连线,然后分成两个子多边形.这显然是不行的,因为计算机已经无法再表示分割出来的子多边形了(不能用f[i,j]来表示了).最优三角形划分•那么我们该如何决策呢?寻找定量!•显然可以发现,f[i,j]表示的子多边形有一条边是在内部的(黑色虚线),而这一条边在该子多边形内必定属于某个三角形,因为我们选择了该子多边形作为一种状态,那么就一定存在那条虚线黑边,所以一定存在所说的三角形.于是我们枚举这个三角形的另外一个点在子多边形的位置,则可以把子问题还原到原问题(因为该三角形把多边形划成了两个可以用表示的多边形和一个三角形).这些再次分割出的子多边形就是以前状态,而刚才的多边形则是当前状态.定量•其实定量的作用就是为了写出状态转移方程,即让人能迅速找出状态之间的关系(决策).通过定量的处理,当前状态又回到了以前状态,选手就可以知道,这一题就是要用动态规划来求解了.定量•我们来看看刚才的一些题目的定量.•