ACM培训第14-15讲_动态规划

1、ACM程序设计第十四-十五讲-动态规划湖南工学院 张新玉目录目录 什么是动态规划 状态 阶段 决策 一种确立状态的方法 两种简单的DP武器 三种特殊的动态规划什么是动态规划什么是动态规划 在学习动态规划之前你一定学在学习动态规划之前你一定学过搜索过搜索.那么搜索与动态规划有那么搜索与动态规划有什么关系呢什么关系呢?我们来下面的一我们来下面的一个例子个例子.数字三角形数字三角形 给你一个数字三角形给你一个数字三角形, 形式如下形式如下: 1 2 3 4 5 67 8 9 10找出从第一层到最后一层的一条找出从第一层到最后一层的一条路路,使得所经过的权值之和最小或使得所经过的权值之和最小或者最大者

2、最大.数字三角形数字三角形 无论对与新手还是老手，这都是再无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们熟悉不过的题了，很容易地，我们写出状态转移方程：写出状态转移方程：f(i, j)=ai, j + minf(i-1, j)+f(i-1, j + 1) 对于动态规划算法解决这个问题，对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

3、式的动态规划就不是那么简单了。 解决方法：解决方法：记忆化搜索记忆化搜索 我们尝试从正面的思路去分析问题，我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递如上例，不难得出一个非常简单的递归过程归过程 : f1:=f(i-1,j+1); f2:=f(i-1,j); if f1f2 then f:=f1+ai,j else f:=f2+ai,j; 显而易见，这个算法就是最简单的搜显而易见，这个算法就是最简单的搜索算法。时间复杂度为索算法。时间复杂度为2n，明显是会，明显是会超时的。分析一下搜索的过程，实际超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是上，很多调用都

4、是不必要的，也就是把产生过的最优状态，又产生了一次。把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一为了避免浪费，很显然，我们存放一个个opt数组：数组： 记忆化搜索记忆化搜索 Opti, j - 每产生一个每产生一个f(i, j)，将，将f(i, j)的值放入的值放入opt中，以后再次调中，以后再次调用到用到f(i, j)的时候，直接从的时候，直接从opti, j来取就可以了。来取就可以了。 于是动态规划的状态转移方程被直于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运的难度，减少了编程的技巧，而运行时

5、间只是相差常数的复杂度，而行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常更好地避免浪费，在比赛中是非常实用的实用的.记忆化的功效动态规划的实质动态规划的实质 可以看出动态规划的实质就是可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满这也就是为什么我们常说动态规划必须满足重叠子问题的原因足重叠子问题的原因.记忆化记忆化,正符合了正符合了这个要求这个要求.状态状态 阶段阶段 决策决策 或许有一种对动态规划的简单或许有一种对动态规划的简单称法称法,叫分阶段决策叫分阶段决策.其实我认其实我认为这个称法并不是很能让人

6、理为这个称法并不是很能让人理解解.那么下面我们来看看阶段那么下面我们来看看阶段,状态状态,决策这三者间得关系吧决策这三者间得关系吧.状态状态 阶段阶段 决策决策 状态是表现出动态规划核心思想的一个东西状态是表现出动态规划核心思想的一个东西.而分阶段决策这个东西有似乎没有提到状态而分阶段决策这个东西有似乎没有提到状态,这是不科学的这是不科学的. 阶段阶段,有些题目并不一定表现出一定的阶段性有些题目并不一定表现出一定的阶段性.数字三角形的阶段就是每一层数字三角形的阶段就是每一层.这里我们引入这里我们引入一个概念一个概念-以前状态以前状态.但阶段不是以前状态但阶段不是以前状态,状态是阶段的表现形式状

7、态是阶段的表现形式.数字三角形的以前状数字三角形的以前状态就是当前层的前一层态就是当前层的前一层. 那什么是决策呢那什么是决策呢?我们看看下面一张图就知道我们看看下面一张图就知道了了.显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。动规的要诀状态动规的要诀状态 我们一般在动规的时候所用到的一我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态些数组，也就是用来存储每个状态的最优值的。的最优值的。 我们就从动态规划的要诀，也就是我们就从动态规划的要诀，也就是核心

8、部分核心部分“状态状态”开始，来逐步了解开始，来逐步了解动态规划。动态规划。拦截导弹拦截导弹 拦截导弹（拦截导弹（Noip2002Noip2002） 某国为了防御敌国的导弹袭击，发展出某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截一种导弹拦截系统。但是这种导弹拦截系统系统 有一个缺陷：虽然它的第一发炮有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一弹能够到达任意的高度，但是以后每一发炮弹都不能高发炮弹都不能高 于前一发的高度。于前一发的高度。 某某天，雷达捕捉到敌国的导弹来袭。由于天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以该系统还在试用阶段，

9、所以 只有一套只有一套系统，因此有可能不能拦截所有的导弹。系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。统最多能拦截多少导弹。拦截导弹拦截导弹 状态的表示状态的表示fi，表示当第，表示当第i个导个导弹必须选择时，前弹必须选择时，前i个导弹最多能拦个导弹最多能拦截多少。截多少。 每个导弹有一定的高度，当前状态每个导弹有一定的高度，当前状态就是以第就是以第i个导弹为最后一个打的导个导弹为最后一个打的导弹。以前状态就是在这个导弹以前弹。以前状态就是在这个导弹以前打的那个导弹。打的那个导弹。 显然这是十分能够体现状态间的联

10、显然这是十分能够体现状态间的联系的题目。系的题目。最长公共子串最长公共子串 给出两个字符串序列。求出这给出两个字符串序列。求出这样的一个最长的公共子串：子样的一个最长的公共子串：子串中的每个字符都能在两个原串中的每个字符都能在两个原串中找到，而且每个字符的顺串中找到，而且每个字符的顺序和原串中的顺序一致。序和原串中的顺序一致。交交错错匹匹配配 交错匹配（最长公共子串的改编）交错匹配（最长公共子串的改编） 给你两排数字给你两排数字, ,只能将两排中数字相同的两个位置只能将两排中数字相同的两个位置相连相连, ,而每次相连必须有两个匹配形成一次交错而每次相连必须有两个匹配形成一次交错, ,交交错的连

11、线不能再和别的交错连线有交点错的连线不能再和别的交错连线有交点. .问这两排问这两排数字最多能形成多少个交错匹配数字最多能形成多少个交错匹配. .2 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 状态的表示状态的表示fi,jfi,j表示前表示前i i个第一排的数个第一排的数字和前字和前j j个第二排的数字搭配的最优值。个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错当前的状态就是当前你枚举到的一组交错的后面两个位置的后面两个位置. .例如上图中当前状态是例如上图中当前状态是3 3和和1(1(第一组交错第一组交错),),枚举他的以前状态就有

12、枚举他的以前状态就有1 1 3.3.这样在这样在1 31 3之前会有一个最优值存在之前会有一个最优值存在, ,因因此可以由此得到此可以由此得到3 13 1的最优值的最优值. .买车票买车票 买车票买车票(Ural1031)(Ural1031) Ekaterinburg Ekaterinburg城到城到SverdlovskSverdlovsk城有城有直线形的铁路线。直线形的铁路线。两城之间还有其他一些停靠站两城之间还有其他一些停靠站, ,总站总站数为数为N N。各站按照离各站按照离EkaterinburgEkaterinburg城的距离城的距离编号。编号。EkaterinburgEkaterin

13、burg城编号为城编号为1 1，SverdlovskSverdlovsk城编号为城编号为N N。买车票买车票某两站之间车票价格由这两站的距离某两站之间车票价格由这两站的距离X X决定决定. . 当当0X=L10X=L1时，票价为时，票价为C1C1元元. . 当当L1X=L2L1X=L2时，票价为时，票价为C2C2元元. . 当当L2X=L3L2X=L3时，票价为时，票价为C3C3元元. .当两站距离大于当两站距离大于L3L3时没有直达票，所以有时候要买几时没有直达票，所以有时候要买几次票做几次车才行。次票做几次车才行。比如，在上面的例图中，比如，在上面的例图中，2-62-6没有直达票，有几种买

14、没有直达票，有几种买票票方法可以从方法可以从2-62-6，其中一种是买，其中一种是买C2C2元的元的2-32-3车票，再买车票，再买C3C3元的元的3-63-6车票。车票。买车票买车票给定起点站和终点站还有给定起点站和终点站还有L1,L2,L3,C1,C2,C3L1,L2,L3,C1,C2,C3，求出要从，求出要从起点到终点最少要花多少钱起点到终点最少要花多少钱. .怎么怎么办办买车票买车票当前所在的某个车站这一题的以前状态其实只有这一题的以前状态其实只有3种种.即即满足满足3种距离种距离(收费收费)情况的情况的3个车站个车站.要知道这要知道这3个车站可以先做一个预个车站可以先做一个预处理处理

15、.显然这显然这3个车站在满足距离限个车站在满足距离限制的条件下应该越远越好制的条件下应该越远越好.买车票买车票 预处理预处理 很容易想出一个很容易想出一个N2的预处理的预处理,但是那样但是那样是会超时的是会超时的.由于尽量要让车站离得远由于尽量要让车站离得远(费用费用是一样的啊是一样的啊 )因此在每种收费情况下因此在每种收费情况下,每个车站的以前状态车站一定是递增的序列每个车站的以前状态车站一定是递增的序列.这里是只要这里是只要O(N)的程序的程序: for j:=1 to 3 do begin k:=en-1; for i:=en downto be do begin while (wayi

16、-wayk=be) do dec(k); pij:=k+1; end; end; 数组数组Pij表示的是表示的是I状态的第状态的第j种以前状态种以前状态.买车票买车票动态规划的部分动态规划的部分for i:=be+1 to en do 枚举当枚举当前状态前状态 begin costi:=maxlongint; for j:=1 to 3 do 枚举枚举以前状态以前状态 beginif (piji) and (costi costpij + cj) then costi:=costpij+cj; end; end;动规的要诀状态动规的要诀状态 有时候当前状态确定后有时候当前状态确定后,以前状以前

17、状态就已经确定态就已经确定,则无需枚举则无需枚举.TomTom的烦恼的烦恼 TomTom是一个非常有创业精神的人，由于大学学的是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的资金开是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂，了一家汽车零件加工厂， 专门为汽车制造商制专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需机器。现在他却遇到了麻烦，多家汽车制造商需要他加要他加 工一些不同零件（由于厂家和零件不同，工一些不同零件（由于厂家和零件不同，所以给的加工费也

18、不同），而且不同厂家对于不所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲甚至是冲突的，但开始和结束时间相同不算冲突）。突）。TomTom当然希望能把所有的零件都加工完，当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量件加工（因为他只有一台机器），为了赚得尽量多的加工费，多的加工费，To

19、mTom不知如何进行取舍。不知如何进行取舍。 TomTom的烦恼的烦恼 Tom的烦恼的烦恼 按结束时间排序，枚举结束时间作按结束时间排序，枚举结束时间作为当前状态为当前状态,以前状态就是该结束时以前状态就是该结束时间对应的起始时间，这是已经确定的间对应的起始时间，这是已经确定的.文字游戏文字游戏 文字游戏文字游戏(fairfox(fairfox邀请赛邀请赛1)1) 给你一份单词表，和一个句子。求出该句子能有多少给你一份单词表，和一个句子。求出该句子能有多少中不同的划分方法中不同的划分方法. .例如例如: : 单词是单词是ab cd a b c dab cd a b c d 句子是句子是abcd

20、abcd 他共有他共有4 4种种完全完全划分方案划分方案: : ab/cd a/b/c/d a/b/cd ab/c/d; ab/cd a/b/c/d a/b/cd ab/c/d; 当前状态就是单词在句子中向后靠的位置当前状态就是单词在句子中向后靠的位置, ,以前状态就以前状态就是确定这个单词位置以后是确定这个单词位置以后, ,除掉这个单词长度后的一除掉这个单词长度后的一个位置个位置. .状态转移方程是状态转移方程是:Fi:=Fi+Fi-:Fi:=Fi+Fi-length(wordj)length(wordj) IOI IOI中有一题中有一题前缀前缀也是类似的题目也是类似的题目. .决策中的定量

21、决策中的定量 状态转移方程的构造无疑是动态状态转移方程的构造无疑是动态规划过程中最重要的一步规划过程中最重要的一步,也是也是最难的一步最难的一步.对于大多数的动态对于大多数的动态规划规划,寻找状态转移方程有一条寻找状态转移方程有一条十分高效的通道十分高效的通道,就是寻找变化就是寻找变化中的不变量中的不变量.定量处理的过程也定量处理的过程也就是决策实施的过程就是决策实施的过程.寻找定量寻找定量 最佳加法表达式最佳加法表达式 有一个由有一个由1.91.9组成的数字串组成的数字串. .问如果将问如果将m m个加号插入到这个个加号插入到这个数字串中数字串中. .使得所形成的算术使得所形成的算术表达式的

22、值最小表达式的值最小. .或许你不明白我在说什么,那么我们通过题目来说明吧最佳加法表达式最佳加法表达式 这一题中的定量是什么呢这一题中的定量是什么呢?因为是添入因为是添入加号加号,那么添完加号后那么添完加号后,表达式的最后一表达式的最后一定是个数字串定是个数字串,这就是定量这就是定量.从这里入手从这里入手,不难发现可以把以前状态认为是在前不难发现可以把以前状态认为是在前i个字符中插入个字符中插入k-1个加号个加号(这里的这里的i是当是当作决策在枚举作决策在枚举),然后然后i+1到最后一位一到最后一位一定是整个没有被分割的数字串定是整个没有被分割的数字串,第第k个加个加号就添在号就添在i与与i+

23、1个数字之间个数字之间.这样就构这样就构造出了整个数字串的最优解造出了整个数字串的最优解.而至于前而至于前i个字符中插入个字符中插入k-1个加号个加号,这又回到了这又回到了原问题的形式原问题的形式,也就是回到了以前状态也就是回到了以前状态,所以状态转移方程就能很快的构造出所以状态转移方程就能很快的构造出来了来了.最佳加法表达式最佳加法表达式 用用fi,j,表示的是在前表示的是在前i个字符中插个字符中插入入j个加号能达到的最小值个加号能达到的最小值,最后的答最后的答案也就是案也就是Flength(s),m. 于是就有一个动规的方程于是就有一个动规的方程: Fi,j:=min(fi,j,fk,j-

24、1+numk+1,i) numk+1,i表示表示k+1位到位到i位所形成的数字位所形成的数字.这里显然这里显然是把加号插入了第是把加号插入了第k+1个位置上个位置上. 知道了这一题怎么做以后知道了这一题怎么做以后,乘积最大乘积最大的一题也是完全一样的形式的一题也是完全一样的形式,谁还会谁还会去用搜索去用搜索?定量定量 现在大概大家已经了解了定量现在大概大家已经了解了定量是什么是什么,那么我们下面通过几那么我们下面通过几道题目来了解一下定量的威力道题目来了解一下定量的威力.游戏游戏 游戏游戏(Noip2003普及组普及组) 这一题的描述简单说一下这一题的描述简单说一下:在一在一个圈的周围有个圈的

25、周围有n个石子个石子,将他们划将他们划分成分成m堆堆(每堆中的石子必须连续每堆中的石子必须连续相邻相邻),每一堆石子计算出他们的每一堆石子计算出他们的总重量总重量mod10的值的值,然后将这些然后将这些值相乘值相乘,求得到的结果最大最小求得到的结果最大最小值是多少值是多少.游戏游戏 这一题作者其实是根据最佳加这一题作者其实是根据最佳加法表达式改编的法表达式改编的.但是他加了一但是他加了一个在圈上的条件个在圈上的条件,怎么办呢怎么办呢?寻找定量!游戏游戏 可想而知可想而知,因为至少要分成因为至少要分成1堆堆,那那么至少有两个石子之间是会被分隔么至少有两个石子之间是会被分隔开的开的.这就是定量这就

26、是定量!当划分数当划分数1时时,一一定有两个相邻石子被划分到不同的定有两个相邻石子被划分到不同的堆里去堆里去! 于是这个圈被这样的理解断成了一于是这个圈被这样的理解断成了一条线条线,解法就和最佳加法表达式一解法就和最佳加法表达式一样了样了. 当然这个断开的位置是需要枚举的当然这个断开的位置是需要枚举的,然后保留下一个最优值然后保留下一个最优值.显然这个显然这个断开的操作对整个过程没有影响断开的操作对整个过程没有影响,因为这是必然的情况因为这是必然的情况,这是定量这是定量!最优三角形划分最优三角形划分 问题描述问题描述 给定一具有给定一具有N N（N50N50）个顶点）个顶点( (从从1 1到到

27、N N编号）的凸多边形，每个顶点编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边的权均已知。问如何把这个凸多边形划分成形划分成N-2N-2个互不相交的三角形，个互不相交的三角形，使得这些三角形顶点的权的乘积之使得这些三角形顶点的权的乘积之和最小？和最小？ 最优三角形划分最优三角形划分 这一题大概搜都是十分麻烦的这一题大概搜都是十分麻烦的,可是可是这一题这一题Dp的话的话,比搜索要容易实现和比搜索要容易实现和容易理解得多容易理解得多. 先得表示一下状态先得表示一下状态,我们用我们用fi,j表示表示以第以第i个点开头个点开头,顺时针长度为顺时针长度为j的一的一块子多边形块子多边形.如上图中

28、如上图中f1,5表示的表示的子多边形子多边形(黑色虚线划开黑色虚线划开)最优三角形划分最优三角形划分 如果没有红色虚线的部分如果没有红色虚线的部分,或许你或许你会认为决策应该是枚举子多边形内会认为决策应该是枚举子多边形内的两点连线的两点连线,然后分成两个子多边然后分成两个子多边形形.这显然是不行的这显然是不行的,因为计算机已因为计算机已经无法再表示分割出来的子多边形经无法再表示分割出来的子多边形了了(不能用不能用fi,j来表示了来表示了).最优三角形划分最优三角形划分 那么我们该如何决策呢那么我们该如何决策呢?寻找定量寻找定量! 显然可以发现显然可以发现,fi,j表示的子多边形表示的子多边形有

29、一条边是在内部的有一条边是在内部的(黑色虚线黑色虚线),而这而这一条边在该子多边形内必定属于某个一条边在该子多边形内必定属于某个三角形三角形,因为我们选择了该子多边形作因为我们选择了该子多边形作为一种状态为一种状态,那么就一定存在那条虚线那么就一定存在那条虚线黑边黑边,所以一定存在所说的三角形所以一定存在所说的三角形.于于是我们枚举这个三角形的另外一个点是我们枚举这个三角形的另外一个点在子多边形的位置在子多边形的位置,则可以把子问题还则可以把子问题还原到原问题原到原问题(因为该三角形把多边形划因为该三角形把多边形划成了两个可以用表示的多边形和一个成了两个可以用表示的多边形和一个三角形三角形).

30、这些再次分割出的子多边形这些再次分割出的子多边形就是以前状态就是以前状态,而刚才的多边形则是当而刚才的多边形则是当前状态前状态.定量定量 其实定量的作用就是为了写出其实定量的作用就是为了写出状态转移方程状态转移方程,即让人能迅速找即让人能迅速找出状态之间的关系出状态之间的关系(决策决策).通过通过定量的处理定量的处理,当前状态又回到了当前状态又回到了以前状态以前状态,选手就可以知道选手就可以知道,这这一题就是要用动态规划来求解一题就是要用动态规划来求解了了.定量定量 我们来看看刚才的一些题目的定量我们来看看刚才的一些题目的定量. 交错匹配交错匹配:一定存在最后一组交错一定存在最后一组交错(这好

31、这好像是废话像是废话),所以枚举这个最后的交错的所以枚举这个最后的交错的位置作为状态位置作为状态,这样就回到以前状态这样就回到以前状态. 买车票买车票:定量定量1:一定有最后一个车站一定有最后一个车站(这这个作为状态个作为状态);定量定量2:某个车站一定是由某个车站一定是由某个前面的车站到达的某个前面的车站到达的.(导弹拦截也是导弹拦截也是这样这样) 数字三角形数字三角形:某个点一定是由他上面的某个点一定是由他上面的相邻两点到达的相邻两点到达的.(过河卒也是这样过河卒也是这样)定量很不错啊!动态规划的武器动态规划的武器 在动规的操作过程中在动规的操作过程中,或者是操或者是操作过程前作过程前,有

32、一些很常用的武器有一些很常用的武器,这里简要介绍两种这里简要介绍两种:排序排序 武器一武器一:排序排序 遇到过很多需要排序的动态规遇到过很多需要排序的动态规划题目划题目,如果不排序如果不排序,动规的思动规的思想很难体现想很难体现.TomTom的烦恼的烦恼 Tom的烦恼的烦恼 这是大家熟知的一题这是大家熟知的一题,如果不如果不排序的话排序的话,复杂度便是复杂度便是N2,按按起始时间排序复杂度也是起始时间排序复杂度也是N2,二按结束时间排序之后复杂度二按结束时间排序之后复杂度降为了降为了NlogN.巴比伦塔巴比伦塔 巴比伦塔巴比伦塔 问题描述问题描述: 有很多的不同种类的立方体有很多的不同种类的立

33、方体(长宽高不同长宽高不同),每一类有无限多每一类有无限多个个.将他们一层层的叠加起来将他们一层层的叠加起来,要要求上面的一块立方体的下底面一求上面的一块立方体的下底面一定要比下面的一块立方体的上底定要比下面的一块立方体的上底面要小面要小,就是长和宽都要小于就是长和宽都要小于.问问最多能建成多高的塔最多能建成多高的塔.巴比伦塔巴比伦塔 经过研究可以发现经过研究可以发现,每一种类的立方每一种类的立方体有体有3种不同的摆放方式种不同的摆放方式,而每种摆而每种摆放方式最多用放方式最多用1次次,所以可以分离出所以可以分离出3*N块块“不同不同”的立方体的立方体,接下来接下来,或或许你仍然不知道如何动规

34、许你仍然不知道如何动规,那么就试那么就试试排序试排序.列出所有的石块的所有摆放列出所有的石块的所有摆放方式方式xi,yi,zi.xi,yi,zi.必须全部保证必须全部保证xiyixiyi.xiyi.然后按关键字然后按关键字xi,yi,zixi,yi,zi的大小顺序排序的大小顺序排序. .这样就可以进行十这样就可以进行十分简单的类似与导弹拦截的一个动分简单的类似与导弹拦截的一个动态规划的处理了态规划的处理了. .限制条件是限制条件是xixi和和yi,yi,代价值是代价值是zi(zi(高度高度).).滑雪滑雪 滑雪滑雪(上海上海2002) 题目的大意是给出一个矩阵题目的大意是给出一个矩阵,如如:对

35、于所给出的矩阵找出一条最长的递减链,满足链中相邻的两个元素间都是在矩阵中相邻的.上图中所给出的矩阵中的最长链是1 2 3 425.滑雪滑雪 对于有给出的数字进行递减排序对于有给出的数字进行递减排序,然后两重循环就搞定问题然后两重循环就搞定问题.动态动态转移方程是转移方程是: Fi:=max(Fi,Fj+1); 满足条件是满足条件是i与与j在原矩阵中相在原矩阵中相邻邻. 试想试想,如果你不知道要排序如果你不知道要排序,你能你能想到这题是用动态规划吗想到这题是用动态规划吗?填鸭填鸭 武器二武器二:填鸭填鸭 这个思想带有枚举的感觉这个思想带有枚举的感觉.就是就是开个大数组开个大数组,把代价值一个个填

36、把代价值一个个填进去进去.硬币问题硬币问题 硬币问题（经典问题）硬币问题（经典问题） 就是给出就是给出n种硬币的面值种硬币的面值,问面值问面值 M有有多少种不同的表示方法多少种不同的表示方法. 动态转移方程是动态转移方程是Fi:=Fi+FI-costj.当前状态是当前状态是i,以前状态是以前状态是i-costj. 多米诺骨牌（某题的简化）多米诺骨牌（某题的简化） 有有N张多米诺骨牌张多米诺骨牌,每张的两端有两个每张的两端有两个数字数字,范围在范围在1.6之间之间.每张骨牌可以正每张骨牌可以正放放,也可以反放也可以反放.求出一种摆放的情况求出一种摆放的情况,使使得所有的骨牌上端数字之和与下端数字

37、得所有的骨牌上端数字之和与下端数字之和的差值最小之和的差值最小.求出最小差值求出最小差值.多米诺骨牌多米诺骨牌可以这么考虑这个问题可以这么考虑这个问题:我们把每一个骨牌的上下差值记我们把每一个骨牌的上下差值记下。接下来的任务便是将这些值下。接下来的任务便是将这些值分成两组，使得他们的和的差值分成两组，使得他们的和的差值最小。动规过程如下：最小。动规过程如下：f0:=true; for i:=1 to n do for j:=sum downto ai do fj:=fj or fj-ai;Sum表示所有差值的和表示所有差值的和. ai表示第表示第i块骨牌块骨牌的差值的差值. J是当前状态是当前

38、状态,j-ai是以前状态是以前状态.fj表示表示j这个差值能否通过组合得到。这个差值能否通过组合得到。接下来的程序就不用我多说了。接下来的程序就不用我多说了。商店购物商店购物 商店购物商店购物(IOI)(IOI) 这一题更是需要开一个五维这一题更是需要开一个五维boolbool型数组型数组. .还需要通过递归还需要通过递归求出组合形式求出组合形式. .动规的方程我动规的方程我就不写了就不写了. .动态规划的武器动态规划的武器|讲完了比较实用的两种种动规的武器之后,我们来看看一些大家可能不太会做的动规类型特殊的动规特殊的动规 这里我讲讲三种特殊的动态规这里我讲讲三种特殊的动态规划划:图状动规图状

39、动规,树状动规树状动规,二次动二次动规规.图状动规图状动规 城堡城堡 某国聪明美丽的公主要找一位如意郎君，某国聪明美丽的公主要找一位如意郎君，她希望未来的夫君是一个聪明善良，节她希望未来的夫君是一个聪明善良，节俭但又不吝啬的人。为了找到理想的人俭但又不吝啬的人。为了找到理想的人选，她的爸爸选，她的爸爸国王，给她修建了一座国王，给她修建了一座城堡，这个城堡有很多房间，房间之间城堡，这个城堡有很多房间，房间之间有走廊连接，但每进入一个房间必须要有走廊连接，但每进入一个房间必须要花费一定数量的钱币，公主就在某个房花费一定数量的钱币，公主就在某个房间中等待。开始，国王给每个候选人一间中等待。开始，国王

40、给每个候选人一样多的钱币，候选人从同一个地点出发，样多的钱币，候选人从同一个地点出发，直到找到美丽的公主为止，如果这时哪直到找到美丽的公主为止，如果这时哪个人找到了公主，并且钱币刚好用完，个人找到了公主，并且钱币刚好用完，那么他将会赢得公主的芳心。那么他将会赢得公主的芳心。城堡城堡 乍看此题乍看此题,似乎就是搜没得说了似乎就是搜没得说了,是吗是吗? 如果告诉你这一题是动态规划如果告诉你这一题是动态规划的话的话,你会怎么做你会怎么做?状态是什状态是什么动态转移方程是什么么动态转移方程是什么?城堡城堡 既然是问我们能不能到达既然是问我们能不能到达,所以所以想想就应该知道想想就应该知道,动规的数组是

41、动规的数组是bool型的型的.一开始时一开始时,只有出发的只有出发的房间记为房间记为true. 但是但是,并不是以每个房间作为状并不是以每个房间作为状态态,因为还存在一个把钱用光的因为还存在一个把钱用光的问题问题.到达同一个房间时到达同一个房间时,如果如果剩余的钱不一样剩余的钱不一样,也就会有不同也就会有不同的决策的决策. 所以状态就是在剩余所以状态就是在剩余j个钱币的个钱币的时候能否到达第时候能否到达第i个房间个房间.用用fi,j来表示来表示.图状动规图状动规于是动态转移方程也就出来了于是动态转移方程也就出来了K表示的是和I连接的一个房间,ci表示进入I号房间的花费.树状动规树状动规 没有上司的晚会没有上司的晚会 某公司要举办一次晚会，但是为某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会个参加晚会的人都不希望在