动态规划专题讲义

1、动态规划专题讲义 |本文只是个人对动态规划的一本文只是个人对动态规划的一 些见解些见解,理论性并不一定能保证理论性并不一定能保证 正确正确,有不足和缺漏之处请谅解有不足和缺漏之处请谅解 和及时地指出和及时地指出. | 是信息学竞赛中选手必是信息学竞赛中选手必 须熟练掌握的一种算法须熟练掌握的一种算法,他以其他以其 多元性广受出题者的喜爱多元性广受出题者的喜爱. 动态规划 |什么是动态规划什么是动态规划 |状态状态 阶段阶段 决策决策 |一种确立状态的方法一种确立状态的方法 |两种简单的动规武器两种简单的动规武器 |三种特殊的动态规划三种特殊的动态规划 |在学习动态规划之前你一定学在学习动态规划

2、之前你一定学 过搜索过搜索.那么搜索与动态规划有那么搜索与动态规划有 什么关系呢什么关系呢?我们来下面的一我们来下面的一 个例子个例子. back |给你一个数字三角形给你一个数字三角形, 形式如下形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条找出从第一层到最后一层的一条 路路,使得所经过的权值之和最小或使得所经过的权值之和最小或 者最大者最大. back |无论对与新手还是老手，这都是再无论对与新手还是老手，这都是再 熟悉不过的题了，很容易地，我们熟悉不过的题了，很容易地，我们 写出状态转移方程：写出状态转移方程：f(i, j)=ai, j + minf(

3、i-1, j)+f(i-1, j + 1) |对于动态规划算法解决这个问题，对于动态规划算法解决这个问题， 我们根据状态转移方程和状态转移我们根据状态转移方程和状态转移 方向，比较容易地写出动态规划的方向，比较容易地写出动态规划的 循环表示方法。但是，当状态和转循环表示方法。但是，当状态和转 移非常复杂的时候，也许写出循环移非常复杂的时候，也许写出循环 式的动态规划就不是那么简单了。式的动态规划就不是那么简单了。 | 解决方法：解决方法： back |我们尝试从正面的思路去分析问题，我们尝试从正面的思路去分析问题， 如上例，不难得出一个非常简单的如上例，不难得出一个非常简单的 递归过程递归过程

4、 : |f1:=f(i-1,j+1); f2:=f(i-1,j); |if f1f2 then f:=f1+ai,j else f:=f2+ai,j; |显而易见，这个算法就是最简单的显而易见，这个算法就是最简单的 搜索算法。时间复杂度为搜索算法。时间复杂度为2n，明显，明显 是会超时的。分析一下搜索的过程，是会超时的。分析一下搜索的过程， 实际上，很多调用都是不必要的，实际上，很多调用都是不必要的， 也就是把产生过的最优状态，又产也就是把产生过的最优状态，又产 生了一次。为了避免浪费，很显然，生了一次。为了避免浪费，很显然， 我们存放一个我们存放一个opt数组：数组： back |Opti,

5、 j - 每产生一个每产生一个f(i, j)， 将将f(i, j)的值放入的值放入opt中，以后再中，以后再 次调用到次调用到f(i, j)的时候，直接从的时候，直接从 opti, j来取就可以了。来取就可以了。 |于是动态规划的状态转移方程被直于是动态规划的状态转移方程被直 观地表示出来了，这样节省了思维观地表示出来了，这样节省了思维 的难度，减少了编程的技巧，而运的难度，减少了编程的技巧，而运 行时间只是相差常数的复杂度，而行时间只是相差常数的复杂度，而 且在相当多的情况下，递归算法能且在相当多的情况下，递归算法能 更好地避免浪费，在比赛中是非常更好地避免浪费，在比赛中是非常 实用的实用的

6、. 记忆化的功效 back |可以看出动态规划的实质就是可以看出动态规划的实质就是 |这也就是为什么我们常说动态这也就是为什么我们常说动态 规划必须满足重叠子问题的原规划必须满足重叠子问题的原 因因.记忆化记忆化,正符合了这个要求正符合了这个要求. |或许有一种对动态规划的简单或许有一种对动态规划的简单 称法称法,叫分阶段决策叫分阶段决策.其实我认为其实我认为 这个称法并不是很能让人理解这个称法并不是很能让人理解. 那么下面我们来看看阶段那么下面我们来看看阶段,状态状态, 决策这三者间得关系吧决策这三者间得关系吧. back |状态是表现出动态规划核心思想的状态是表现出动态规划核心思想的 一个

7、东西一个东西.而分阶段决策这个东西有而分阶段决策这个东西有 似乎没有提到状态似乎没有提到状态,这是不科学的这是不科学的. |阶段阶段,有些题目并不一定表现出一定有些题目并不一定表现出一定 的阶段性的阶段性.数字三角形的阶段就是每数字三角形的阶段就是每 一层一层.这里我们引入一个概念这里我们引入一个概念-以前以前 状态状态.但阶段不是以前状态但阶段不是以前状态,状态是状态是 阶段的表现形式阶段的表现形式.数字三角形的以前数字三角形的以前 状态就是当前层的前一层状态就是当前层的前一层. |那什么是决策呢那什么是决策呢?我们看看下面一我们看看下面一 张图就知道了张图就知道了. back 决策 显然,

8、从上图可以看出,当前状态通 过决策,回到了以前状态.可见决策 其实就是状态之间的桥梁。而以前 状态也就决定了当前状态的情况。 数字三角形的决策就是选择相邻的两 个以前状态的最优值。 back |我们一般在动规的时候所用到的一我们一般在动规的时候所用到的一 些数组，也就是用来存储每个状态些数组，也就是用来存储每个状态 的最优值的。的最优值的。 |我们就从动态规划的要诀，也就是我们就从动态规划的要诀，也就是 核心部分核心部分“状态状态”开始，来逐步了开始，来逐步了 解动态规划。解动态规划。 back |拦截导弹（拦截导弹（Noip2002Noip2002） |某国为了防御敌国的导弹袭击，发某国为了

9、防御敌国的导弹袭击，发 展出一种导弹拦截系统。但是这种展出一种导弹拦截系统。但是这种 导弹拦截系统导弹拦截系统 有一个缺陷：虽然它有一个缺陷：虽然它 的第一发炮弹能够到达任意的高度，的第一发炮弹能够到达任意的高度， 但是以后每一发炮弹都不能高但是以后每一发炮弹都不能高 于前于前 一发的高度。一发的高度。 某天，雷达捕捉到敌某天，雷达捕捉到敌 国的导弹来袭。由于该系统还在试国的导弹来袭。由于该系统还在试 用阶段，所以用阶段，所以 只有一套系统，因此只有一套系统，因此 有可能不能拦截所有的导弹。输入有可能不能拦截所有的导弹。输入 导弹依次飞来的高度，计算这套系导弹依次飞来的高度，计算这套系 统最多

10、能拦截多少导弹。统最多能拦截多少导弹。 |状态的表示状态的表示fi，表示当第，表示当第i个导个导 弹必须选择时，前弹必须选择时，前i个导弹最多能拦个导弹最多能拦 截多少。截多少。 |每个导弹有一定的高度，当前状态每个导弹有一定的高度，当前状态 就是以第就是以第i个导弹为最后一个打的导个导弹为最后一个打的导 弹。以前状态就是在这个导弹以前弹。以前状态就是在这个导弹以前 打的那个导弹。打的那个导弹。 |显然这是十分能够体现状态间的联显然这是十分能够体现状态间的联 系的题目。系的题目。 back |给出两个字符串序列。求出这给出两个字符串序列。求出这 样的一个最长的公共子串：子样的一个最长的公共子串

11、：子 串中的每个字符都能在两个原串中的每个字符都能在两个原 串中找到，而且每个字符的顺串中找到，而且每个字符的顺 序和原串中的顺序一致。序和原串中的顺序一致。 |交错匹配（最长公共子串的改编）交错匹配（最长公共子串的改编） 给你两排数字给你两排数字, ,只能将两排中数字相同的两个位置只能将两排中数字相同的两个位置 相连相连, ,而每次相连必须有两个匹配形成一次交错而每次相连必须有两个匹配形成一次交错, ,交交 错的连线不能再和别的交错连线有交点错的连线不能再和别的交错连线有交点. .问这两排问这两排 数字最多能形成多少个交错匹配数字最多能形成多少个交错匹配. . 2 3 3 2 4 1 5 1

12、 3 5 10 3 1 2 3 2 4 12 1 5 5 3 状态的表示状态的表示fi,jfi,j表示前表示前i i个第一排的数个第一排的数 字和前字和前j j个第二排的数字搭配的最优值。个第二排的数字搭配的最优值。 当前的状态就是当前你枚举到的一组交错当前的状态就是当前你枚举到的一组交错 的后面两个位置的后面两个位置. .例如上图中当前状态是例如上图中当前状态是3 3 和和1(1(第一组交错第一组交错),),枚举他的以前状态就有枚举他的以前状态就有1 1 3.3.这样在这样在1 31 3之前会有一个最优值存在之前会有一个最优值存在, ,因因 此可以由此得到此可以由此得到3 13 1的最优值的

13、最优值. . back |买车票买车票(Ural1031)(Ural1031) Ekaterinburg Ekaterinburg城到城到SverdlovskSverdlovsk 城有直线形的铁路线。城有直线形的铁路线。 两城之间还有其他一些停靠站两城之间还有其他一些停靠站, , 总站数为总站数为N N。 各站按照离各站按照离EkaterinburgEkaterinburg城的城的 距离编号。距离编号。 EkaterinburgEkaterinburg城编号为城编号为1 1， SverdlovskSverdlovsk城编号为城编号为N N。 back 某两站之间车票价格由这两站的距离某两站之间

14、车票价格由这两站的距离X X决定决定. . 当当0X=L10X=L1时，票价为时，票价为C1C1元元. . 当当L1X=L2L1X=L2时，票价为时，票价为C2C2元元. . 当当L2X=L3L2X=L3时，票价为时，票价为C3C3元元. . 当两站距离大于当两站距离大于L3L3时没有直达票，所以有时候要买几时没有直达票，所以有时候要买几 次票做几次车才行。次票做几次车才行。 比如，在上面的例图中，比如，在上面的例图中，2-62-6没有直达票，有几种买票没有直达票，有几种买票 方法可以从方法可以从2-62-6，其中一种是买，其中一种是买C2C2元的元的2-32-3车票，再买车票，再买 C3C3

15、元的元的3-63-6车票。车票。 back 给定起点站和终点站还有给定起点站和终点站还有 L1,L2,L3,C1,C2,C3L1,L2,L3,C1,C2,C3，求出要从，求出要从 起点到终点最少要花多少钱起点到终点最少要花多少钱. . 怎么办怎么办 back 当前状态 以前状态 当前所在的某个车站 这一题的以前状态其实只有这一题的以前状态其实只有3种种.即即 满足满足3种距离种距离(收费收费)情况的情况的3个车站个车站. 要知道这要知道这3个车站可以先做一个预个车站可以先做一个预 处理处理.显然这显然这3个车站在满足距离限个车站在满足距离限 制的条件下应该越远越好制的条件下应该越远越好. ba

16、ck |预处理预处理 很容易想出一个很容易想出一个N2的预处理的预处理,但是那但是那 样是会超时的样是会超时的.由于尽量要让车站离得由于尽量要让车站离得 远远(费用是一样的啊费用是一样的啊 )因此在每种收因此在每种收 费情况下费情况下,每个车站的以前状态车站一每个车站的以前状态车站一 定是递增的序列定是递增的序列.这里是只要这里是只要O(N)的程的程 序序: for j:=1 to 3 do begin k:=en-1; for i:=en downto be do begin while (wayi-wayk=be) do dec(k); pij:=k+1; end; end; 数组数组Pi

17、j表示的是表示的是I状态的第状态的第j种以前状态种以前状态. back 动态规划的部分动态规划的部分 for i:=be+1 to en do 枚举当前状态枚举当前状态 begin costi:=maxlongint; for j:=1 to 3 do 枚举以前状态枚举以前状态 begin if (piji) and (costi costpij + cj) then costi:=costpij+cj; end; end; back |有时候当前状态确定后有时候当前状态确定后,以前状以前状 态就已经确定态就已经确定,则无需枚举则无需枚举. back |TomTom是一个非常有创业精神的人，由

18、于大是一个非常有创业精神的人，由于大 学学的是汽车制造专业，所以毕业后他学学的是汽车制造专业，所以毕业后他 用有限的资金开了一家汽车零件加工厂，用有限的资金开了一家汽车零件加工厂， 专门为汽车制造商制造零件。由于资金专门为汽车制造商制造零件。由于资金 有限，他只能先购买一台加工机器。现有限，他只能先购买一台加工机器。现 在他却遇到了麻烦，多家汽车制造商需在他却遇到了麻烦，多家汽车制造商需 要他加要他加 工一些不同零件（由于厂家和零工一些不同零件（由于厂家和零 件不同，所以给的加工费也不同），而件不同，所以给的加工费也不同），而 且不同厂家对于不同零件的加工时间要且不同厂家对于不同零件的加工时间

19、要 求不同（有些加工时间要求甚至是冲突求不同（有些加工时间要求甚至是冲突 的，但开始和结束时间相同不算冲突）。的，但开始和结束时间相同不算冲突）。 TomTom当然希望能把所有的零件都加工完，当然希望能把所有的零件都加工完， 以得到更多的加工费，但当一些零件的以得到更多的加工费，但当一些零件的 加工时间要求有冲突时，在某个时间内加工时间要求有冲突时，在某个时间内 他只能选择某种零件加工（因为他只有他只能选择某种零件加工（因为他只有 一台机器），为了赚得尽量多的加工费，一台机器），为了赚得尽量多的加工费， TomTom不知如何进行取舍。不知如何进行取舍。 |Tom的烦恼的烦恼 按结束时间排序，枚

20、举结束时间作为按结束时间排序，枚举结束时间作为 当前状态当前状态,以前状态就是该结束时间对以前状态就是该结束时间对 应的起始时间，这是已经确定的应的起始时间，这是已经确定的. back |文字游戏文字游戏(fairfox(fairfox邀请赛邀请赛1)1) 给你一份单词表，和一个句子。求出该句给你一份单词表，和一个句子。求出该句 子能有多少中不同的划分方法子能有多少中不同的划分方法. .例如例如: : 单词是单词是ab cd a b c dab cd a b c d 句子是句子是abcdabcd 他共有他共有4 4种完全划分方案种完全划分方案: : ab/cd a/b/c/d a/b/cd a

21、b/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中有一题中有一题前缀前缀也是类似的题目也是类似的题目. . |状态转移方程的构造无疑是动态状态转移方程的构造无疑是动态 规划过程中最重要的一步规划过程中最重要的一步,也是

22、也是 最难的一步最难的一步.对于大多数的动态对于大多数的动态 规划规划,寻找状态转移方程有一条寻找状态转移方程有一条 十分高效的通道十分高效的通道,就是寻找变化就是寻找变化 中的不变量中的不变量.定量处理的过程也定量处理的过程也 就是决策实施的过程就是决策实施的过程. back |最佳加法表达式最佳加法表达式 |有一个由有一个由1.91.9组成的数字串组成的数字串. . 问如果将问如果将m m个加号插入到这个个加号插入到这个 数字串中数字串中. .使得所形成的算术使得所形成的算术 表达式的值最小表达式的值最小. . Problem 或许你不明白我在说什么,那 么我们通过题目来说明吧 back

23、|这一题中的定量是什么呢这一题中的定量是什么呢?因为是添因为是添 入加号入加号,那么添完加号后那么添完加号后,表达式的最表达式的最 后一定是个数字串后一定是个数字串,这就是定量这就是定量.从这从这 里入手里入手,不难发现可以把以前状态认不难发现可以把以前状态认 为是在前为是在前i个字符中插入个字符中插入k-1个加号个加号 (这里的这里的i是当作决策在枚举是当作决策在枚举),然后然后i+1 到最后一位一定是整个没有被分割到最后一位一定是整个没有被分割 的数字串的数字串,第第k个加号就添在个加号就添在i与与i+1个个 数字之间数字之间.这样就构造出了整个数字这样就构造出了整个数字 串的最优解串的最

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

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

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

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

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

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

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

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

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

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

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

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

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

37、觉这个思想带有枚举的感觉.就是就是 开个大数组开个大数组,把代价值一个个填把代价值一个个填 进去进去. back |硬币问题（经典问题）硬币问题（经典问题） 就是给出就是给出n种硬币的面值种硬币的面值,问面值问面值 M 有多少种不同的表示方法有多少种不同的表示方法. 动态转移方程是动态转移方程是Fi:=Fi+FI- costj.当前状态是当前状态是i,以前状态是以前状态是i- costj. |多米诺骨牌（某题的简化）多米诺骨牌（某题的简化） 有有N张多米诺骨牌张多米诺骨牌,每张的两端有两每张的两端有两 个数字个数字,范围在范围在1.6之间之间.每张骨牌可每张骨牌可 以正放以正放,也可以反放也可

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

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

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

41、个房一定数量的钱币，公主就在某个房 间中等待。开始，国王给每个候选间中等待。开始，国王给每个候选 人一样多的钱币，候选人从同一个人一样多的钱币，候选人从同一个 地点出发，直到找到美丽的公主为地点出发，直到找到美丽的公主为 止，如果这时哪个人找到了公主，止，如果这时哪个人找到了公主， 并且钱币刚好用完，那么他将会赢并且钱币刚好用完，那么他将会赢 得公主的芳心。得公主的芳心。 back |乍看此题乍看此题,似乎就是搜没得说了似乎就是搜没得说了, 是吗是吗? |如果告诉你这一题是动态规划如果告诉你这一题是动态规划 的话的话,你会怎么做你会怎么做?状态是什状态是什 么动态转移方程是什么么动态转移方程是

42、什么? back |既然是问我们能不能到达既然是问我们能不能到达,所以所以 想想就应该知道想想就应该知道,动规的数组是动规的数组是 bool型的型的.一开始时一开始时,只有出发的只有出发的 房间记为房间记为true. |但是但是,并不是以每个房间作为状并不是以每个房间作为状 态态,因为还存在一个把钱用光的因为还存在一个把钱用光的 问题问题.到达同一个房间时到达同一个房间时,如果剩如果剩 余的钱不一样余的钱不一样,也就会有不同的也就会有不同的 决策决策. |所以状态就是在剩余所以状态就是在剩余j个钱币的个钱币的 时候能否到达第时候能否到达第i个房间个房间.用用fi,j 来表示来表示. back

43、于是动态转移方程也就出来了于是动态转移方程也就出来了 K表示的是和I连接的一个房 间,ci表示进入I号房间的花费. back |没有上司的晚会没有上司的晚会 |某公司要举办一次晚会，但是某公司要举办一次晚会，但是 为了使得晚会的气氛更加活跃，为了使得晚会的气氛更加活跃， 每个参加晚会的人都不希望在每个参加晚会的人都不希望在 晚会中见到他的上司，要不然晚会中见到他的上司，要不然 他们会很扫兴。现在已知每个他们会很扫兴。现在已知每个 人的活跃指数和上司关系（当人的活跃指数和上司关系（当 然不可能存在环），求邀请哪然不可能存在环），求邀请哪 些人来能使得晚会的总活跃指些人来能使得晚会的总活跃指 数最

44、大。数最大。 back |按照要求构建一张关系图，可按照要求构建一张关系图，可 见这是一棵树。对于这类最值见这是一棵树。对于这类最值 问题，向来是用动态规划求解问题，向来是用动态规划求解 的。的。 |任何一个点的取舍可以看作一任何一个点的取舍可以看作一 种决策，那么状态就是在某个种决策，那么状态就是在某个 点取的时候或者不取的时候，点取的时候或者不取的时候， 以他为跟的子树能有的最大活以他为跟的子树能有的最大活 跃总值。分别可以用跃总值。分别可以用fi,1和和 fi,0表示。表示。 back |当这个点取的时候，他的所有当这个点取的时候，他的所有 儿子都不能取，所以儿子都不能取，所以 fi,1

45、:=sum(fj,0,j为为i的儿子的儿子) i的权值。的权值。 |不取的时候，他的所有儿子取不取的时候，他的所有儿子取 不取无所谓，不过当然应该取不取无所谓，不过当然应该取 价值最大的一种情况。所以价值最大的一种情况。所以 fi,0:=sum(max(fj,1,fj,0),j 为为i的的i儿子）。儿子）。 |这就是树状动规的基本形态。这就是树状动规的基本形态。 back |在动规的基础上再进行动规，就叫在动规的基础上再进行动规，就叫 做二次动规。做二次动规。 |买票买票 |有一座有一座n层的楼房，某个人要到第层的楼房，某个人要到第n 层的任何一个房间买票。每层楼都层的任何一个房间买票。每层楼

46、都 有有m个房间。而如果要到第个房间。而如果要到第i层的第层的第j 个房间买票，那么必须先在第个房间买票，那么必须先在第i-1层层 的第的第j个房间买票或者在第个房间买票或者在第i层的与这层的与这 个房间相邻的房间买过票才行个房间相邻的房间买过票才行.而每而每 个房间所要收取的票费是不同的个房间所要收取的票费是不同的,给给 定每个房间内买票需要的费用定每个房间内买票需要的费用,问要问要 在第在第n层的任意一间房间内买到票的层的任意一间房间内买到票的 最小消费是多少最小消费是多少. back |显然不能写这样的状态转移方显然不能写这样的状态转移方 程程:fi,j:=min(fi-1,j,fi,j

47、-1,fi,j+1)+wj. 因为无法有一种处理顺序使得在因为无法有一种处理顺序使得在fi,j之前之前 同时求得同时求得fi,j-1和和fi,j+1的最优值的最优值. |所以动规分两次进行所以动规分两次进行.第一次用状态转移第一次用状态转移 方程方程fi,j:=min(fi,j-1,fi-1,j)+wi求出一求出一 个不一定是最优的解个不一定是最优的解.再用再用 fi,j:=min(fi,j,fi,j+1,j from m-1 downto 1)+wi求出最终的最优解求出最终的最优解,可以证可以证 明这样的能够求出真正的最优解明这样的能够求出真正的最优解. |要注意的是这两次动规不能分开做要注

48、意的是这两次动规不能分开做,而要而要 在处理每一层的时候都要做在处理每一层的时候都要做,要不然显然要不然显然 无法求得最优值。无法求得最优值。 back |网络（网络（Ural1056,求树的中心）求树的中心） |题目大意是：题目大意是：有一棵有有一棵有N个结个结 点的树，给出每个结点的父亲点的树，给出每个结点的父亲 （即给出这棵树），边的权都（即给出这棵树），边的权都 是是1。每个结点延树的边可以。每个结点延树的边可以 走到树的任意一个结点，令走到树的任意一个结点，令Ai 为第为第i个结点最远能走的距离，个结点最远能走的距离， 求出求出Ai最小的结点有哪些。如最小的结点有哪些。如 有多个最小

49、的有多个最小的Ai，则都要输出。，则都要输出。 这里这里N=10000N=10000 back |枚举每个点，然后枚举每个点，然后DFS复杂度复杂度O(N2)， 超时是显然的事情。超时是显然的事情。 |可以发现其实有很多可以发现其实有很多DFS都重复做都重复做 了同样的工作，产生了浪费，所以了同样的工作，产生了浪费，所以 应该选择动态规划解决这个问题。应该选择动态规划解决这个问题。 |树上的动规，是否直接可以写出下树上的动规，是否直接可以写出下 面的状态转移方城呢？面的状态转移方城呢？ |fi:=max(fson,ffather)+1 |废话，显然是不行的，废话，显然是不行的，son和和fat

50、her 的值不可能同时得到。的值不可能同时得到。 |但是不要放弃，解决这个冲突的方但是不要放弃，解决这个冲突的方 法，就是采用二次动规。法，就是采用二次动规。 back |第一次动规做第一次动规做fi:=max(fson)+1， 第二次动规做第二次动规做fi:=max(fi,ffather + 1) 。 |但是存在一个问题就是如果但是存在一个问题就是如果ffather 的值是从的值是从i那里得到的，这样计算显那里得到的，这样计算显 然就错了。然就错了。 |不要放弃，在实际操作过程中，不要放弃，在实际操作过程中，f需需 要记下两个值，一个是最优值，一要记下两个值，一个是最优值，一 个是次优值，这两个值必须由不用个是次优值，这两个值必须由不用 的子结点得到。这样当最优值发生的子结点得到。这样当最优值发生 矛盾的时候，次优值一定不会矛盾。矛盾的时候，次优值一定不会矛盾。 问题就解决了。复杂度问题就解决了。复杂度O(N)O(N)十分的十分的 理想。理想。 back |动态规划有很多东西还需要我们动态规划有很多东西还需要我们 更加努力地去探索和学习更加努力地去探索和学习.总体总体 上说来上说来,动态规划是个既简单又动态规划是个既简单又 不简单的算法不简单的算法,熟练地掌握了动熟练