资源描述：
《浙江大学acm程序设计竞赛动态规划讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划专题讲义前言本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.动态规划是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.动态规划目录什么是动态规划状态阶段决策一种确立状态的方法两种简单的动规武器三种特殊的动态规划什么是动态规划在学习动态规划之前你一定学过搜索.那么搜索与动态规划有什么关系呢?我们来下面的一个例子.back数字三角形给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.back数字三角形无论对与新手还是老手
2、，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。解决方法：back记忆化搜索记忆化搜索我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程:f1:=f(i-1,j+1);f2:=f(i-1,j);iff1>f2thenf:=f1+a[i,j]elsef:=f2+a[i,j];显而
3、易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：back记忆化搜索Opt[i,j]-每产生一个f(i,j)，将f(i,j)的值放入opt中，以后再次调用到f(i,j)的时候，直接从opt[i,j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.记忆化的
4、功效back动态规划的实质可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子问题的原因.记忆化,正符合了这个要求.记忆化搜索状态阶段决策或许有一种对动态规划的简单称法,叫分阶段决策.其实我认为这个称法并不是很能让人理解.那么下面我们来看看阶段,状态,决策这三者间得关系吧.back状态阶段决策状态是表现出动态规划核心思想的一个东西.而分阶段决策这个东西有似乎没有提到状态,这是不科学的.阶段,有些题目并不一定表现出一定的阶段性.数字三角形的阶段就是每一层.这里我们引入一个概念---以前状态.但阶段不是以前状态,状态是阶段的表现形式.数字三角形
5、的以前状态就是当前层的前一层.那什么是决策呢?我们看看下面一张图就知道了.back决策当前状态以前状态决策显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。back动规的要诀－状态我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。back拦截导弹拦截导弹（Noip2002）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系
6、统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。拦截导弹状态的表示－f[i]，表示当第i个导弹必须选择时，前i个导弹最多能拦截多少。每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个打的导弹。以前状态就是在这个导弹以前打的那个导弹。显然这是十分能够体现状态间的联系的题目。back最长公共子串给出两个字符串序列。求出这样的一个最长的公共子串：子串中的每
7、个字符都能在两个原串中找到，而且每个字符的顺序和原串中的顺序一致。交错匹配交错匹配（最长公共子串的改编）给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错,交错的连线不能再和别的交错连线有交点.问这两排数字最多能形成多少个交错匹配.233241513510312324121553状态的表示－f[i,j]表示前i个第一排的数字和前j个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错的后面两个位置.例如上图中当前状态是3和1(第一组交错),枚举他的以前状态就有13.这样在13之前会有一个最优值存在,因此可以由此得
8、到31的最优值.back买车票买车票(Ural103
