动态规划专题讲义解读.ppt

动态规划专题讲义 前言 本文只是个人对动态规划的一些见解 理论性并不一定能保证正确 有不足和缺漏之处请谅解和及时地指出 动态规划 是信息学竞赛中选手必须熟练掌握的一种算法 他以其多元性广受出题者的喜爱 动态规划 目录 什么是动态规划状态阶段决策一种确立状态的方法两种简单的动规武器三种特殊的动态规划 什么是动态规划 在学习动态规划之前你一定学过搜索 那么搜索与动态规划有什么关系呢 我们来下面的一个例子 back 数字三角形 给你一个数字三角形 形式如下 12345678910找出从第一层到最后一层的一条路 使得所经过的权值之和最小或者最大 back 数字三角形 无论对与新手还是老手 这都是再熟悉不过的题了 很容易地 我们写出状态转移方程 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 显而易见 这个算法就是最简单的搜索算法 时间复杂度为2n 明显是会超时的 分析一下搜索的过程 实际上 很多调用都是不必要的 也就是把产生过的最优状态 又产生了一次 为了避免浪费 很显然 我们存放一个opt数组 back 记忆化搜索 Opt i j 每产生一个f i j 将f i j 的值放入opt中 以后再次调用到f i j 的时候 直接从opt i j 来取就可以了 于是动态规划的状态转移方程被直观地表示出来了 这样节省了思维的难度 减少了编程的技巧 而运行时间只是相差常数的复杂度 而且在相当多的情况下 递归算法能更好地避免浪费 在比赛中是非常实用的 记忆化的功效 back 动态规划的实质 可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子问题的原因 记忆化 正符合了这个要求 记忆化搜索 状态阶段决策 或许有一种对动态规划的简单称法 叫分阶段决策 其实我认为这个称法并不是很能让人理解 那么下面我们来看看阶段 状态 决策这三者间得关系吧 back 状态阶段决策 状态是表现出动态规划核心思想的一个东西 而分阶段决策这个东西有似乎没有提到状态 这是不科学的 阶段 有些题目并不一定表现出一定的阶段性 数字三角形的阶段就是每一层 这里我们引入一个概念 以前状态 但阶段不是以前状态 状态是阶段的表现形式 数字三角形的以前状态就是当前层的前一层 那什么是决策呢 我们看看下面一张图就知道了 back 决策 当前状态 以前状态 决策 显然 从上图可以看出 当前状态通过决策 回到了以前状态 可见决策其实就是状态之间的桥梁 而以前状态也就决定了当前状态的情况 数字三角形的决策就是选择相邻的两个以前状态的最优值 back 动规的要诀 状态 我们一般在动规的时候所用到的一些数组 也就是用来存储每个状态的最优值的 我们就从动态规划的要诀 也就是核心部分 状态 开始 来逐步了解动态规划 back 拦截导弹 拦截导弹 Noip2002 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 计算这套系统最多能拦截多少导弹 拦截导弹 状态的表示 f i 表示当第i个导弹必须选择时 前i个导弹最多能拦截多少 每个导弹有一定的高度 当前状态就是以第i个导弹为最后一个打的导弹 以前状态就是在这个导弹以前打的那个导弹 显然这是十分能够体现状态间的联系的题目 back 最长公共子串 给出两个字符串序列 求出这样的一个最长的公共子串 子串中的每个字符都能在两个原串中找到 而且每个字符的顺序和原串中的顺序一致 交错匹配 交错匹配 最长公共子串的改编 给你两排数字 只能将两排中数字相同的两个位置相连 而每次相连必须有两个匹配形成一次交错 交错的连线不能再和别的交错连线有交点 问这两排数字最多能形成多少个交错匹配 233241513510312324121553 状态的表示 f i j 表示前i个第一排的数字和前j个第二排的数字搭配的最优值 当前的状态就是当前你枚举到的一组交错的后面两个位置 例如上图中当前状态是3和1 第一组交错 枚举他的以前状态就有13 这样在13之前会有一个最优值存在 因此可以由此得到31的最优值 back 买车票 买车票 Ural1031 Ekaterinburg城到Sverdlovsk城有直线形的铁路线 两城之间还有其他一些停靠站 总站数为N 各站按照离Ekaterinburg城的距离编号 Ekaterinburg城编号为1 Sverdlovsk城编号为N back 买车票 某两站之间车票价格由这两站的距离X决定 当0 X L1时 票价为C1元 当L1 X L2时 票价为C2元 当L2 X L3时 票价为C3元 当两站距离大于L3时没有直达票 所以有时候要买几次票做几次车才行 比如 在上面的例图中 2 6没有直达票 有几种买票方法可以从2 6 其中一种是买C2元的2 3车票 再买C3元的3 6车票 back 买车票 给定起点站和终点站还有L1 L2 L3 C1 C2 C3 求出要从起点到终点最少要花多少钱 怎么办 确定题目的当前状态与以前状态 back 买车票 当前状态 以前状态 当前所在的某个车站 这一题的以前状态其实只有3种 即满足3种距离 收费 情况的3个车站 要知道这3个车站可以先做一个预处理 显然这3个车站在满足距离限制的条件下应该越远越好 back 买车票 预处理很容易想出一个N 2的预处理 但是那样是会超时的 由于尽量要让车站离得远 费用是一样的啊 因此在每种收费情况下 每个车站的以前状态车站一定是递增的序列 这里是只要O N 的程序 forj 1to3dobegink en 1 fori endowntobedobeginwhile way i way k be dodec k p i j k 1 end end 数组P i j 表示的是I状态的第j种以前状态 back 买车票 动态规划的部分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 back 动规的要诀 状态 有时候当前状态确定后 以前状态就已经确定 则无需枚举 back Tom的烦恼 Tom是一个非常有创业精神的人 由于大学学的是汽车制造专业 所以毕业后他用有限的资金开了一家汽车零件加工厂 专门为汽车制造商制造零件 由于资金有限 他只能先购买一台加工机器 现在他却遇到了麻烦 多家汽车制造商需要他加工一些不同零件 由于厂家和零件不同 所以给的加工费也不同 而且不同厂家对于不同零件的加工时间要求不同 有些加工时间要求甚至是冲突的 但开始和结束时间相同不算冲突 Tom当然希望能把所有的零件都加工完 以得到更多的加工费 但当一些零件的加工时间要求有冲突时 在某个时间内他只能选择某种零件加工 因为他只有一台机器 为了赚得尽量多的加工费 Tom不知如何进行取舍 Tom的烦恼 Tom的烦恼按结束时间排序 枚举结束时间作为当前状态 以前状态就是该结束时间对应的起始时间 这是已经确定的 back 文字游戏 文字游戏 fairfox邀请赛1 给你一份单词表 和一个句子 求出该句子能有多少中不同的划分方法 例如 单词是abcdabcd句子是abcd他共有4种完全划分方案 ab cda b c da b cdab c d 当前状态就是单词在句子中向后靠的位置 以前状态就是确定这个单词位置以后 除掉这个单词长度后的一个位置 状态转移方程是 F i F i F i length word j IOI中有一题 前缀 也是类似的题目 决策中的定量 状态转移方程的构造无疑是动态规划过程中最重要的一步 也是最难的一步 对于大多数的动态规划 寻找状态转移方程有一条十分高效的通道 就是寻找变化中的不变量 定量处理的过程也就是决策实施的过程 寻找定量 back 寻找定量 最佳加法表达式有一个由1 9组成的数字串 问如果将m个加号插入到这个数字串中 使得所形成的算术表达式的值最小 Problem 或许你不明白我在说什么 那么我们通过题目来说明吧 back 最佳加法表达式 这一题中的定量是什么呢 因为是添入加号 那么添完加号后 表达式的最后一定是个数字串 这就是定量 从这里入手 不难发现可以把以前状态认为是在前i个字符中插入k 1个加号 这里的i是当作决策在枚举 然后i 1到最后一位一定是整个没有被分割的数字串 第k个加号就添在i与i 1个数字之间 这样就构造出了整个数字串的最优解 而至于前i个字符中插入k 1个加号 这又回到了原问题的形式 也就是回到了以前状态 所以状态转移方程就能很快的构造出来了 back 最佳加法表达式 用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个位置上 知道了这一题怎么做以后 乘积最大的一题也是完全一样的形式 谁还会去用搜索 back 定量 现在大概大家已经了解了定量是什么 那么我们下面通过几道题目来了解一下定量的威力 back 游戏 游戏 Noip2003普及组 这一题的描述简单说一下 在一个圈的周围有n个石子 将他们划分成m堆 每堆中的石子必须连续相邻 每一堆石子计算出他们的总重量mod10的值 然后将这些值相乘 求得到的结果最大最小值是多少 back 游戏 这一题作者其实是根据最佳加法表达式改编的 但是他加了一个在圈上的条件 怎么办呢 寻找定量 back 游戏 可想而知 因为至少要分成1堆 那么至少有两个石子之间是会被分隔开的 这就是定量 当划分数 1时 一定有两个相邻石子被划分到不同的堆里去 于是这个圈被这样的理解断成了一条线 解法就和最佳加法表达式一样了 当然这个断开的位置是需要枚举的 然后保留下一个最优值 显然这个断开的操作对整个过程没有影响 因为这是必然的情况 这是定量 back 最优三角形划分 问题描述给定一具有N N 50 个顶点 从1到N编号 的凸多边形 每个顶点的权均已知 问如何把这个凸多边形划分成N 2个互不相交的三角形 使得这些三角形顶点的权的乘积之和最小 back 最优三角形划分 这一题大概搜都是十分麻烦的 可是这一题Dp的话 比搜索要容易实现和容易理解得多 先得表示一下状态 我们用f i j 表示以第i个点开头 顺时针长度为j的一块子多边形 如上图中f 1 5 表示的子多边形 黑色虚线划开 back 最优三角形划分 如果没有红色虚线的部分 或许你会认为决策应该是枚举子多边形内的两点连线 然后分成两个子多边形 这显然是不行的 因为计算机已经无法再表示分割出来的子多边形了 不能用f i j 来表示了 back 最优三角形划分 那么我们该如何决策呢 寻找定量 显然可以发现 f i j 表示的子多边形有一条边是在内部的 黑色虚线 而这一条边在该子多边形内必定属于某个三角形 因为我们选择了该子多边形作为一种状态 那么就一定存在那条虚线黑边 所以一定存在所说的三角形 于是我们枚举这个三角形的另外一个点在子多边形的位置 则可以把子问题还原到原问题 因为该三角形把多边形划成了两个可以用表示的多边形和一个三角形 这些再次分割出的子多边形就是以前状态 而刚才的多边形则是当前状态 back 定量 其实定量的作用就是为了写出状态转移方程 即让人能迅速找出状态之间的关系 决策 通过定量的处理 当前状态又回到了以前状态 选手就可以知道 这一题就是要用动态规划来求解了 back 定量 我们来看看刚才的一些题目的定量 交错匹配 一定存在最后一组交错 这好像是废话 所以枚举这个最后的交错的位置作为状态 这样就回到以前状态 买车票 定量1 一定有最后一个车站 这个作为状态 定量2 某个车站一定是由某个前面的车站到达的 导弹拦截也是这样 数字三角形 某个点一定是由他上面的相邻两点到达的 过河卒也是这样 定量很不错啊 动态规划的武器 在动规的操作过程中 或者是操作过程前 有一些很常用的武器 这里简要介绍两种 排序 填鸭 back 排序 武器一 排序遇到过很多需要排序的动态规划题目 如果不排序 动规的思想很难体现 back Tom的烦恼 Tom的烦恼这是大家熟知的一题 如果不排序的话 复杂度便是N 2 按起始时间排序复杂度也是N 2 二按结束时间排序之后复杂度降为了NlogN back 巴比伦塔 巴比伦塔问题描述 有很多的不同种类的立方体 长宽高不同 每一类有无限多个 将他们一层层的叠加起来 要求上面的一块立方体的下底面一定要比下面的一块立方体的上底面要小 就是长和宽都要小于 问最多能建成多高的塔 back 巴比伦塔 经过研究可以发现 每一种类的立方体有3种不同的摆放方式 而每种摆放方式最多用1次 所以可以分离出3 N块 不同 的立方体 接下来 或许你仍然不知道如何动规 那么就试试排序 列出所有的石块的所有摆放方式xi yi zi 必须全部保证xiyi 然后按关键字xi yi zi的大小顺序排序 这样就可以进行十分简单的类似与导弹拦截的一个动态规划的处理了 限制条件是xi和yi 代价值是zi 高度 back 滑雪 滑雪 上海2002 题目的大意是给出一个矩阵 如 对于所给出的矩阵找出一条最长的递减链 满足链中相邻的两个元素间都是在矩阵中相邻的 上图中所给出的矩阵中的最长链是1234 25 back 滑雪 对于有给出的数字进行递减排序 然后两重循环就搞定问题 动态转移方程是 F i max F i F j 1 满足条件是i与j在原矩阵中相邻 试想 如果你不知道要排序 你能想到这题是用动态规划吗 back 填鸭 武器二 填鸭这个思想带有枚举的感觉 就是开个大数组 把代价值一个个填进去 back 硬币问题 硬币问题 经典问题 就是给出n种硬币的面值 问面值M有多少种不同的表示方法 动态转移方程是F i F i F I cost j 当前状态是i 以前状态是i cost j 多米诺骨牌 某题的简化 有N张多米诺骨牌 每张的两端有两个数字 范围在1 6之间 每张骨牌可以正放 也可以反放 求出一种摆放的情况 使得所有的骨牌上端数字之和与下端数字之和的差值最小 求出最小差值 back 多米诺骨牌 可以这么考虑这个问题 我们把每一个骨牌的上下差值记下 接下来的任务便是将这些值分成两组 使得他们的和的差值最小 动规过程如下 f 0 true fori 1tondoforj sumdowntoa i dof j f j orf j a i Sum表示所有差值的和 a i 表示第i块骨牌的差值 J是当前状态 j a i 是以前状态 f j 表示j这个差值能否通过组合得到 接下来的程序就不用我多说了 back 商店购物 商店购物 IOI 这一题更是需要开一个五维bool型数组 还需要通过递归求出组合形式 动规的方程我就不写了 back 动态规划的武器 讲完了比较实用的两种种动规的武器之后 我们来看看一些大家可能不太会做的动规类型 特殊的动规 这里我讲讲三种特殊的动态规划 图状动规 树状动规 二次动规 back 图状动规 城堡某国聪明美丽的公主要找一位如意郎君 她希望未来的夫君是一个聪明善良 节俭但又不吝啬的人 为了找到理想的人选 她的爸爸 国王 给她修建了一座城堡 这个城堡有很多房间 房间之间有走廊连接 但每进入一个房间必须要花费一定数量的钱币 公主就在某个房间中等待 开始 国王给每个候选人一样多的钱币 候选人从同一个地点出发 直到找到美丽的公主为止 如果这时哪个人找到了公主 并且钱币刚好用完 那么他将会赢得公主的芳心 back 城堡 乍看此题 似乎就是搜没得说了 是吗 如果告诉你这一题是动态规划的话 你会怎么做 状态是什么动态转移方程是什么 back 城堡 既然是问我们能不能到达 所以想想就应该知道 动规的数组是bool型的 一开始时 只有出发的房间记为true 但是 并不是以每个房间作为状态 因为还存在一个把钱用光的问题 到达同一个房间时 如果剩余的钱不一样 也就会有不同的决策 所以状态就是在剩余j个钱币的时候能否到达第i个房间 用f i j 来表示 back 图状动规 于是动态转移方程也就出来了 f i j f i j orf k j c i K表示的是和I连接的一个房间 c i 表示进入I号房间的花费 back 树状动规 没有上司的晚会某公司要举办一次晚会 但是为了使得晚会的气氛更加活跃 每个参加晚会的人都不希望在晚会中见到他的上司 要不然他们会很扫兴 现在已知每个人的活跃指数和上司关系 当然不可能存在环 求邀请哪些人来能使得晚会的总活跃指数最大 back 没有上司的晚会 按照要求构建一张关系图 可见这是一棵树 对于这类最值问题 向来是用动态规划求解的 任何一个点的取舍可以看作一种决策 那么状态就是在某个点取的时候或者不取的时候 以他为跟的子树能有的最大活跃总值 分别可以用f i 1 和f i 0 表示 back 没有上司的晚会 当这个点取的时候 他的所有儿子都不能取 所以f i 1 sum f j 0 j为i的儿子 i的权值 不取的时候 他的所有儿子取不取无所谓 不过当然应该取价值最大的一种情况 所以f i 0 sum max f j 1 f j 0 j为i的i儿子 这就是树状动规的基本形态 back 二次动规 在动规的基础上再进行动规 就叫做二次动规 买票有一座n层的楼房 某个人要到第n层的任何一个房间买票 每层楼都有m个房间 而如果要到第i层的第j个房间买票 那么必须先在第i 1层的第j个房间买票或者在第i层的与这个房间相邻的房间买过票才行 而每个房间所要收取的票费是不同的 给定每个房间内买票需要的费用 问要在第n层的任意一间房间内买到票的最小消费是多少 back 买票 显然不能写这样的状态转移方程 f i j min f i 1 j f i j 1 f i j 1 w j 因为无法有一种处理顺序使得在f i j 之前同时求得f i j 1 和f i j 1 的最优值 所以动规分两次进行 第一次用状态转移方程f i j min f i j 1 f i 1 j w i 求出一个不一定是最优的解 再用f i j min f i j f i j 1 jfromm 1downto1 w i 求出最终的最优解 可以证明这样的能够求出真正的最优解 要注意的是这两次动规不能分开做 而要在处理每一层的时候都要做 要不然显然无法求得最优值 back 综合题 网络 Ural1056 求树的中心 题目大意是 有一棵有N个结点的树 给出每个结点的父亲 即给出这棵树 边的权都是1 每个结点延树的边可以走到树的任意一个结点 令Ai为第i个结点最远能走的距离 求出Ai最小的结点有哪些 如有多个最小的Ai 则都要输出 这里N 10000 back 网络 枚举每个点 然后DFS复杂度O N2 超时是显然的事情 可以发现其实有很多DFS都重复做了同样的工作 产生了浪费 所以应该选择动态规划解决这个问题 树上的动规 是否直接可以写出下面的状态转移方城呢 f i max f son f father 1废话 显然是不行的 son和father的值不可能同时得到 但是不要放弃 解决这个冲突的方法 就是采用二次动规 back 网络 第一次动规做f i max f son 1 第二次动规做f i max f i f father 1 但是存在一个问题就是如果f father 的值是从i那里得到的 这样计算显然就错了 不要放弃 在实际操作过程中 f需要记下两个值 一个是最优值 一个是次优值 这两个值必须由不用的子结点得到 这样当最优值发生矛盾的时候 次优值一定不会矛盾 问题就解决了 复杂度O N 十分的理想 back 总结 动态规划有很多东西还需要我们更加努力地去探索和学习 总体上说来 动态规划是个既简单又不简单的算法 熟练地掌握了动态规划 也就熟练地控制了比赛 back That sall Thankyouforlistening back 动规练习题 垃圾陷阱 USACO TJU1087 卡门 农夫约翰极其珍视的一条Holsteins奶牛 已经落了到 垃圾井 中 垃圾井 是农夫们扔垃圾的地方 它的深度为D 2 D 100 英尺 卡门想把垃圾堆起来 等到堆得与井同样高时 她就能逃出井外了 另外 卡门可以通过吃一些垃圾来维持自己的生命 每个垃圾都可以用来吃或堆放 并且堆放垃圾不用花费卡门的时间 假设卡门预先知道了每个垃圾扔下的时间t 0 t 1000 以及每个垃圾堆放的高度h 1 h 25 和吃进该垃圾能维持生命的时间f 1 f 30 要求出卡门最早能逃出井外的时间 假设卡门当前体内有足够持续10小时的能量 如果卡门10小时内没有进食 卡门就将饿死 动规练习题 字符串距离 TJU1086 设有字符串X 我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串 如字符串X为 abcbcd 则字符串 abcb cd a bcbcd 和 abcb cd 都是X的扩展串 这里 代表空格字符 如果A1是字符串A的扩展串 B1是字符串B的扩展串 A1与B1具有相同的长度 那么我们定义字符串A1与B1的距离为相应位置上