动态规划思想.pptx

动态规划思想 纲要 动态规划概念动态规划思路 顺推和逆推状态压缩的动态规划树型动态规划动态规划优化四边形不等式剪枝队列优化 凸单调性优化 动态规划算法的适用范围 最优子结构最优决策序列的字序列也是最优的无后效性决策只取决于当前状态的特征因素 而和到达此状态的方式无关 递推 将最优性变成统计的动态规划 递推同样需要状态的划分和无后效性但是递推的转移函数 状态转移方程 通常不包括max和min 而是一些统计函数 如求和递推的难点通常在状态建模和转移函数的确定综上所述 将递推看成动态规划的一种形式是没问题的因此 接下来的内容将不区别动态规划和递推 思路 核心思想 提取信息的共性 将影响到今后状态决策的信息提取出来 提取的信息要尽可能精简 信息提取的思路可以从搜索开始设想寻找一个合适的顺序去求得每个状态 弱化阶段的概念 一个简单例子 排队 2008年北京网络预赛题 n个小朋友排队 每个小朋友都不一样高 两个小朋友a和b能够互相看见当且仅当排在它们中间的小朋友比a和b都要矮 已知队伍中一共有m对小朋友可以互相看见 问有可能有多少种排队方式 数据范围 n 80 m 10000 一个简单例子 排队 2008年北京网络预赛题 思路方式 怎么提取信息的共性 无从下手 创造一种方式 从下一步做起提取共性 信息的冗余 去除冗余信息后 原来的若干搜索状态合并为一个 一个简单例子 排队 2008年北京网络预赛题 是否存在更好的方法 换一种顺序思考 提取信息的共性 从上面的分析可以看出 动态规划可以看成是对搜索的一种记忆化优化动态规划需要尽量使得搜索的状态保存的信息尽可能的精简 说白了就是搜索的总状态数越少越好 这一点和搜索是相同的和搜索不同的是 动态规划会需要按照某种特定的顺序 寻找合适的顺序 这里讲的顺序分为两种 第一种是按照什么样的顺序求出每个状态的值 第二种是按照什么样的顺序来进行状态转移 或者说 状态转移方程的写法 倒推 最长不降子序列 寻找求得当前状态f i 的方法F 0 0 For i 1 if i f i f j 1 顺推 最长不降子序列 根据当前状态f i 寻找能够更新的状态For i 1 if j 顺推思想的应用 由于习惯性 几乎所有的动态规划书上都使用了倒推形式的状态转移方程 这导致大多数动态规划顺推 倒推思想都能用 但是 在很多时候 使用顺推思路会方便很多 顺推思路的一个基本应用 dijstra 游泳 09年合肥赛区试题 给定一个N M 1来表示 那么下一秒Facer将到达 垂直速度会因变速器而改变 因水平速度永远不变 因此以后提到 速度 都指的是垂直速度 游泳 09年合肥赛区试题 Facer每到一个格子都可以设法改变自己的的速度v 将其 1 1 也可以不改变 如果一个格子内有变速器 那么速度v也会发生改变 改变量等于该变速器的加速值 加速值可正可负 因此 假如Facer当前速度为v 他所在的格子中变速器的加速值为k 那么下一秒钟 Facer可能位于 或者 要注意 泳池的深度为N 即如果Facer碰到了池底 那么算作Facer在池底 如果Facer浮出水面 则算作Facer恰好在水面 也就是说 若计算得出 Facer当前的位置应为 若x N 则Facer实际上会位于 同理 若x Facer的速度v会维持 除非Facer自己改变或者碰到变速器 但还有一个例外 无论Facer当前的速度v是多少 如果Facer位于水面 第一行 则因为水面张力 Facer的速度v会瞬间变成0 Facer不能长时间憋气 他需要每K秒浮出一下水面 也就是说 Facer不能连续K秒使得自己的位置中的x不为1 你需要找出一种方法使得Facer能够到达右上角 在此前提下Facer得到的钱越多越好 可能是负数 输出最多的钱数 游泳 09年合肥赛区试题 解题思路 本题的考察点是两个时间复杂度的分析算法的灵活运用 关键是提取信息的共性要善于利用顺推思维 传统思维 以每一列为阶段需要保存的信息有当前的行 列当前的速度当前是第几秒钟没有呼吸了状态转移 顺推型 逆推型 新的思维 分析时间复杂度 发现问题信息共性 重新提取换一种模型 不保存呼吸 行 速度等信息新的算法 动态规划 搜索转移思路 顺推 总结 有些时候不知道本状态会由哪些状态转移过来 但是知道本状态会对哪些状态产生影响 这种时候就是和用顺推思路 而不是死板硬套形式化的状态转移方程的倒推思路根据时间复杂度分析 合理选择模型也很重要 状态压缩的动态规划 前文提到过了信息的提取 通常需要提取的信息不会很多 是多项式级别的 但例外总是有的有些时候需要提取的某些信息不是多项式级别的 而是指数级别的 于是就有了状态压缩的动态规划因此 从算法思路上考虑 状态压缩的动态规划 也只不过就是想出一种办法来表示指数级别的信息而已 多维信息表示法 多进制数 例如 如果想表示一个5维的信息 每一维的范围是 1 3 那么 可以用一个5位的三进制数来表示 写程序时 写两个三进制数和一个长度为5的一维数组之间的转换函数如果是 1 2 或者 1 4 那么 可以使用位运算来进行转换 POJ1185炮兵阵地 司令部的将军们打算在N M的网格地图上部署他们的炮兵部队 一个N M的地图由N行M列组成 地图的每一格可能是山地 用 H 表示 也可能是平原 用 P 表示 如下图 在每一格平原地形上最多可以布置一支炮兵部队 山地上不能够部署炮兵部队 一支炮兵部队在地图上的攻击范围如图中黑色区域所示 POJ1185炮兵阵地 如果在地图中的灰色所标识的平原上部署一支炮兵部队 则图中的黑色的网格表示它能够攻击到的区域 沿横向左右各两格 沿纵向上下各两格 图上其它白色网格均攻击不到 从图上可见炮兵的攻击范围不受地形的影响 现在 将军们规划如何部署炮兵部队 在防止误伤的前提下 保证任何两支炮兵部队之间不能互相攻击 即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内 在整个地图区域内最多能够摆放多少我军的炮兵部队 数据范围 1 n 100 1 m 10 解题思路 我们先假设用搜索来做 看看需要保存那些有用的信息有用的信息 当前搜索到的行 列以及最下面的炮的摆放位置调整一下结构 以行为单位 那么 有用的信息就是当前的行号 以及当前行的炮的摆放状态状态转移方式 顺推无疑状态转移方程 搜索完成下一行的摆放状态状态的表示 二进制数表示多维 时间复杂度分析 每一行状态最多2的10次方约1000个 因此最多100 1000 100000状态转移需要搜索下一行的状态 最多需要枚举2的10次方约1000个状态100 1000 1000 100000000超时 NO 脱出监狱 2010年杭州试题 给定一个N M的迷宫 1 N M 15 Facer是一个机器人 迷宫中的每个格子 矩阵的每个元素 可能是下面几个之一 墙 Facer不能进入该格子平地 Facer可以随意进入该格 进入后没有事情发生开关 迷宫中一共有K个开关 Facer必须经过所有这K个格子至少1次 把这些开关都打开 当Facer到达第K个开关的时候 Facer就能立刻飞出迷宫 能量池 Facer一开始拥有一个容量为T的电池 初始时Facer的电池是充满了电的 每到一个能量池的时候 Facer可以选择是否给你的电池 充电 如果选择充电 则该能量池被消耗 该格子变成平地 且同时Facer的电池能量回复到满电量T 脱出监狱 2010年杭州试题 Facer在迷宫中每行走一步需要耗费1个单位的电量 且仅有行走会耗费电量 电池没电时如果Facer仍未完成任务则会死亡 电量恰好为0时 若Facer在能量池上 则可以立即充电不算死亡 每一次行走能够向上下左右任意一个方向行走一格的距离 现在问 Facer是否有可能走出迷宫 如果有可能 那么Facer的电池容量T最小为多少 题目中保证开关和能量池的总数不超过15 解题思路 提取需要的信息 发现连搜索都无从下手在最大容量不固定的情况下 本体无从下手 于是乎只能 枚举答案分析 一定需要枚举吗 换一种高效的方式是否可行 比如说 二分 已知电池容量的情况下 整理需要保存的信息优化一下 发现一个规律 最短路猜想 解题思路 模型转换 转换成另外一个图模型需要保存的信息当前处于什么位置当前有哪些能量池用过了 当前有哪些开关打开了 不超过15个布尔信息 可以使用一个二进制数来表示 时间复杂度分析 状态 15 2的15次方状态转移 15总时间复杂度15 15 2的15次方 大约1千万 可以接受 综合练习题 大萌战 作为一个动漫粉丝 你需要带领你的队伍参加一个叫做萌战的游戏 你的队伍有四个角色 Saber 凛 樱和伊利亚 你的目标是通过这次的萌战赚取尽可能多的KID KID是某动漫论坛的论坛币 萌战的规则如下 除开你的队伍之外 还有其它N支队伍也参与了萌战 每只队伍由4个角色构成 你需要和每只其它的队伍打一轮 所以你一共要打N轮比赛 每轮对阵一支不同的队伍 综合练习题 大萌战 每轮萌战分为三场 每一场都是你的一个角色与对方的一个角色PK 当然同一轮里面一个角色不能上多场 也就是说 你在每一轮比赛中需要从你的四个角色中选出三个来 并安排她们的出场顺序 你可以假定你的敌人的出场人物和出场顺序是完全随机的 即你的敌人的每个角色都有同样的可能性出现在这一轮 并有同样的可能性出现在某一场上 每一轮结束后你需要将下一轮的出场名单和出场顺序提交 综合练习题 大萌战 萌战结束后 你所得KID与下面两个因素相关 1 你一共赢的场数 当然你最多能赢3N场 最少0场 赢得场数越多所得KID越多 2 你的最大 连胜数 如果你的一个角色在某一段时间内连胜了若干场而没有败过 那么你可以拿到额外的KID 当然连胜不一定要每轮都出场了 例如 你的Saber在第一 第二 第四轮都赢了但是第三轮你没让她上 那么Saber就有了一个三连胜 但是若Saber第三轮上场了并且输了 那么她只有二连胜 你所得的KID就是上面两者之和 输入数据会给你有关场次数和连胜数的两张表 你需要用来计算最后得到的KID 连胜数最多为M 超过M场连胜的话 你得到的奖励和M场连胜一样多 综合练习题 大萌战 每个角色都拥有一个 萌力值 拥有较高 萌力值 的角色总能打败较低 萌力值 的角色 如果两个角色 萌力值 一样那么双方都有50 的概率获胜 你知道所有参赛角色的 萌力值 你足够聪明 在每一轮结束后的提交名单时 总会使用最好的策略使得期望得到的KID最多 那么 请问按照期望 你能得到的KID是多少 数据范围 对于所有测试数据 有1 N 30 0 M 5 输入样例 假设N 2 你的4个角色战斗力分别为15 25 35 45第一支敌军战斗力为10 20 30 40第二支敌军战斗力为10 20 30 40连胜1场奖励100 两场奖励200最终获胜场次奖励为20 40 60 80 100 120 信息提取 先假设使用搜索 那么肯定是搜每一场的决策了每一场的决策是什么 本题和上述几个普通动归的明显区别在哪 本题是个求解的过程 上述几题都是推导的过程对后面有影响的信息是哪些 对后面的影响是什么 对得分的影响 当前的轮数 赢了的场数 每个人当前的连胜数 以及当前最大连胜数 信息提取 本题不是顺推 并非用当前状态去推导后面的状态 但是本题使用了顺推思想 为了求得当前状态的值 需要使用后面的某些状态的值 而后面的某些状态的值需要被先求出来说白了 本题的求值顺序是倒着的 倒推 但是需要求哪些值 每个值是如何来的得从顶部开始推实现方式为记忆化搜索 解题思路 用f I j k l 表示当前是第i轮 已经赢了j场 最大连胜为k 每个人的连胜场数用一个长度为4的M 1进制数l表示时的期望得KID数目标是求得f 1 0 0 0 为了求出它 我们需要枚举当前的决策 派哪3个人上场 然后 会得到一个继续下去的公式 最后选择最大的一个决策即可 思考 增加一个规则允许你贿赂某些队伍 告诉你贿赂每支队伍所需要的钱 如果你贿赂了那支队伍 那么你将能够安排地方的出场人物和出场顺序 同样 问你期望得KID数是多少 总结 一种动态规划 包括状态压缩 思维方式假设用搜索 寻找需要保存的信息精简这些信息 发现共性寻找一种顺序 求得每个状态的值 可以顺推 也可以逆推 看哪种方便 动态规划的优化 动态规划的优化通常可以比较明显的分成两类降低时间复杂度的优化 通常称为降维不一定降低时间复杂度的优化 可以称为剪枝并不是说降维一定比剪枝好 许多动态规划的剪枝空间还是很大的但是剪枝通常没有固定的方法 需要的是大量经验 因此 这里着重讲动态规划的降维 动态规划的降维 四边形不等式使用队列 栈等线性数据结构降维 使用较高级的数据结构降维 凸 凹 完全单调性 四边形不等式 2D 1D模型介绍 假设数据范围为n状态数为n n状态转移方程复杂度为O n 则称当前的模型为2D 1D的 四边形不等式最常见得使用就是在2D 1D模型中 四边形不等式 2D 1D模型有下列常见的状态转移方程形式d i j min d i k 1 d k 1 j w i j 其中 若w满足不等式w a c w b d w b c w a d a b c d 则称w满足四边形不等式 四边形不等式 相关定理 定理一 若w满足四边形不等式 则d满足四边形不等式定理二 设让d i j 取得最小值的k 路径 为K i j 则有k i j 1 k i j k i 1 j w满足四边形不等式当且仅当w i j w i 1 j 1 w i 1 j w i j 1 四边形不等式 如何降维 根据定理二 可以在动态规划的过程中记录路径 然后 在求d I j 的过程中 k的枚举只需要在K i 1 j 和K I j 1 之间即可 也就是说 从d I 1 到d I m k总共只枚举了O m 的量级 因此整体的时间复杂度是O n 2 四边形不等式 但是 我们在实际做题过程中 一般都不会去严格推导或者证明四边形不等式一般使用四边形不等式 都是根据经验 直觉 来判断但是 这些判断也有一些根据在这里 我只能稍微讲一些典型的四边形不等式例题 而准确的使用需要经验的积累 四边形不等式 经典例题 邮局问题 有n个村庄 在一条直线上 告诉你每个村庄的位置 现在需要在这些村庄里建m个邮局 使得所有村庄到最近的邮局的路程总和最小 四边形不等式 经典例题 邮局问题 初始模型的建立如何分块 最后一块的选择有没有什么特点 根据不严格的推导 直奔定理二 四边形不等式 四边形不等式 经典例题 最优二分检索树 给出n个数据a1 a2 an和他们的频数f1 f2 fn 构造一棵二分检索树T 使得每个数据的深度di与fi乘积之和最小 四边形不等式 经典例题 最优二分检索树 先建立2D 1D模型再考虑决策的选择是否有某种规律 从抽象的模型出发 尝试暂时摒弃具体的推导 动态规划经典例题MILK 给定m种砝码 每种砝码ai个 需要知道1克 2克 n克这些重量的物体能否秤出 M 10000 n 10000 ai 10000 动态规划经典例题MILK 很常见的一类动态规划题先不考虑时间复杂度 请给出一个动态规划建模方案 动态规划经典例题MILK 考虑到时间复杂度 我们至少需要达到什么样的效果 原方案中哪里有冗余 发现了什么 如何优化 线性数据结构降维 经典例题advertise 地上并排插着n块木板 每块木板高度为ai 宽度为1 请在这些木板上画出一个长方形用于广告 使得这个长方形的面积最大 数据范围n 1000000 线性数据结构降维 经典例题advertise 先考虑简单想法将想法细致化 问题可以简化至什么程度 结合数据结构 如何优化 线性数据结构降维 小结 通常有一个浅显的建模 不一定哦O O 转移方程有可优化的余地接下来 需要观察更进一步 有可能需要计算和推导基本要求 需要对各种基础数据结构 融会贯通 栈 队列 线性数据结构降维 parade 08年北京regional 国王想要游览整个城市 城市有一个n m矩阵形状的交通路线 已知国王游览的 大方向 是从南向北 即绝不向南走 且不会经过重复的地方两次或以上 每条东西向的街道都有一个权值 可以是负数 表示国民对国王的欢迎程度 问你如何设计游行路线 能够使得国王在游行的过程中受欢迎程度最高 每条东西向的街道都有一个长度 国王讨厌总是往同一个方向行走超过L米 你必须满足他的要求 线性数据结构降维 parade 08年北京regional 一个样例 如图 a b 表示该街道欢迎度为a 长度为b当L 2时 最佳游览路线如黑线所示 数据范围n 100 m 10000 L 3000000 线性数据结构降维 parade 08年北京regional 如何建立一个简单的动态规划模型 出题者的考察点应该是什么 线性数据结构降维 parade 08年北京regional 时间复杂度能否达到要求 状态转移是否有优化的可能 问题较复杂 能否拆分 决策的确定有着什么样的充要条件 线性数据结构降维 parade 08年北京regional 需要考虑什么特殊情况 边界条件 线性数据结构降维 总结 复杂的问题先分开来看细致的分析需要严格推导呆板的数据结构需要灵活运用 线性数据结构降维 总结 栈 一端进出队列 一端进 一端出建模 请不要按规则进出 树型动归 通常会出现这样的问题 给一棵树 要求以最少的代价 或取得最大收益 完成给定的操作有很多问题都是在树和最优性的基础上进行了扩充和加强 从而变成了棘手的问题这类问题通常规模较大 枚举算法的效率无法胜任 贪心算法不能得到最优解 因此要用动态规划解决 树型动归 建模 简单细节 繁琐编程 复杂 IOI05河流 n个伐木的村庄 组成一棵有向树 边的方向为从儿子到父亲 在0号结点有一个巨大的伐木场 木料被砍下后 顺着河流而被运到0号结点的伐木场为了减少运输木料的费用 再额外建造k个伐木场这些伐木场建造后 木料可以在运输过程中第一个碰到的新伐木场被处理 要使总运输费用最小 问题描述 所有的河流都不会分叉 也就是说 每一个村子 顺流而下都只有一条路到0号结点 已知每个村子每年要产多少木料 求在哪些村子建设伐木场能获得最小的运费 N 100K 50 问题抽象 数据范围N 100建立k个伐木厂 使得把所有木材运送到最近的祖先伐木厂的费用最小 由于题目给定的是一棵树 数据规模又比较大 很容易联想到树型动态规划 模型的建立 树型DP90 以上的建模思维法则 子树建模本子树需要什么 本子树会影响什么 模型的建立 F I j k I 子树J 本子树里有多少伐木场K 本子树需要哪个 外地 伐木场 状态的转移 分情况讨论 在本子树的根建立伐木厂不在本子树的根建立伐木厂新的问题问题抽象解决方案 时间复杂度分析 状态数O N 3 转移复杂度O N 总体复杂度O N 4 思考 时间复杂度能说明什么 回顾 建模 子树建模 阶段性思维 后效性思维状态转移 分情况讨论 将困难的问题拆解开来 进行第二次动态规划复杂度分析 理论结合实际 超级广场 09年合肥赛区现场赛试题 题目简述 一个国家 有N个城市 有道路连接着这些城市 组成了一棵树 每个城市有人口数目 每条道路有长度你需要选择一些城市建立超级广场 一共可以建M个目的是使得所有人到最近的超级广场的路程之和最小限制条件 所有的超级广场必须相连 任意两个超级广场都存在一条路径 该路径仅经过包含超级广场的城市 模型的建立 子树建模思维本子树需要什么 本子树会影响什么 模型的建立 F I j 如果本子树有超级广场I 子树J 超级广场个数如果本子树没有超级广场I 子树J 0还需要记录什么 状态的转移 分情况讨论在根节点建立超级广场不在根节点建立超级广场新的问题又来了 继续问题抽象解决方案 时间复杂度分析 状态数目O nm 状态转移O m 总体时间复杂度O nm 2 树型动态规划总结 建模 简单的定势思维状态划分 阶段性思维状态转移 将大问题化成小问题复杂度分析 不要拘泥于表面总之 大局上看似简单 实则复杂 细节上不要怕麻烦 根据实际情况思考问题 谢谢大家 瑰丽华尔兹 NOI2005 一个N行M列的矩阵 矩阵中的某些方格上堆放了一些家具 其他的则是空地 有一台钢琴在初始位置 x0 y0 并且可以在空地上滑动 但不能撞上家具或滑出舞厅 每个时刻 钢琴都会随着船体倾斜的方向向相邻的方格滑动一格