动态规划的分类解析.ppt

动态规划 动态规划 什么是动态规划动态规划的条件动态规划的关键几种常见动态规划的种类例题分析 什么是动态规划 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题被重复计算了许多次 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 由此不难得出结论 动态规划实质就是 记忆化搜索 下面这个数塔的例子将形象地向我们展示这样的结论给你一个数字三角形 形式如下 1238518142110找出从第一层到最后一层的一条路 使得所经过的权值之和最小或者最大 当然 大家都很清楚的知道转移方程为opt i j max opt i 1 j opt i 1 j 1 a i j 边界条件特殊处理即可 但只要仔细想想就会发现 这不过是一个加了强力剪枝的记忆化搜索而已 因为每个点我们只记录到当前节点的最优解 因此省去了大量的重复计数和明显不是最优解的情况 从而使运行速度有了极大的优化 动态规划的条件 而在求解的过程中一道能使用动规解决的题必须具备以下几个条件无后效性 即某阶段的状态一旦确定 则此后过程的演变不再受此前各状态及决策的影响 也就是说 未来与过去无关 当前的状态是此前历史的一个完整总结 此前的历史只能通过当前的状态去影响过程未来的演变 满足最优子结构性质 即一个问题的最优解必须是在子问题取得最优解的情况下决策出来的 动态规划的过程可以简单地描述为 找出最优解的性质 并刻画其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 动态规划的关键 有明确的状态状态转移方程清晰正确 几种常见动规的种类 线性动规背包问题 区间动规树形动规 下面让我们通过几个例子来了解这些基本动规的思考方法 拦截导弹 Noip2002 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 计算这套系统最多能拦截多少导弹 状态的确定 状态的表示 f i 表示当第i个导弹必须拦截时 前i个导弹中最多能拦截多少 每个导弹有一定的高度 当前状态就是以第i个导弹为最后一个拦截的导弹 以前状态就是在这个导弹之前拦截的那个导弹 对于f i 我们考察在i之前位置的导弹 找到所有可以连接上的导弹k 即满足其高度大于等于第i个导弹 选择其中f k 值最大的一个 f i f k 1 如果没有满足条件的k 则f i 1 这是线性动态规划的经典例题 代码 for inti 1 i a i mx max mx f j 1 f i mx intans 0 for inti 1 i n i ans max ans f i printf d n ans 最低通行费 一个商人穿过一个N N的正方形的网格 去参加一个非常重要的商务活动 他要从网格的左上角进 右下角出 每穿越中间1个小方格 都要花费1个单位时间 商人必须在 2N 1 个单位时间穿越出去 而在经过中间的每个小方格时 都需要缴纳一定的费用 这个商人期望在规定时间内用最少费用穿越出去 请问至少需要多少费用 注意 不能对角穿越各个小方格 即 只能向上下左右四个方向移动且不能离开网格 最低通行费 输入第一行是一个整数 表示正方形的宽度N 1 N 100 后面N行 每行N个不大于100的整数 为网格上每个小方格的费用 输出至少需要的费用 分析 这个问题的关键在于发现对移动方向的限制 即由于必须在 2N 1 单位时间内完成移动 因此仅能向下或者向右移动 当移动方向限定后 不难看出这个问题就是变形的数塔问题 于是可以借助动态规划高效解决 状态的确定 我们用opt i j 表示从左上角入口移动到第i行j列的最小代价 则opt i j min opt i 1 j opt i j 1 a i j 最后输出opt n n 代码 for inti 1 i n i for intj 1 j n j scanf d 乘积最大 国际数学联盟确定的 2000 世界数学年 又恰逢我国著名数学家华罗庚先生诞辰90周年 在华罗庚先生的家乡江苏金坛 组织了一场别开生面的数学智力竞赛活动 你的好朋友XZ也有幸得以参加 活动中 主持人给所有参加活动的选手出了这样一道题目 设有一个长度为N N 40 的数字串 要求选手使用M M 6 个乘号将它分成M 1个部分 找出一种分法 使得这M 1个部分的乘积最大 同时 为了帮助选手能够理解题意 主持人还举了如下一个例子 有一个数字串 312 当N 3 M 1时会有两种分法 3 12 36 31 2 62这时 符合题目要求的结果是 31 2 62 现在 请你帮助你的好朋友XZ设计一个程序 求得正确的答案 分析 由于自然数位数的上限为40 乘号数的上限为6 因此最大乘积位数的上限接近42位 显然 运算任何整数类型都无法容纳如此之大的数据 只能采用高精度运算 限于篇幅 对于高精度的加法运算 乘法运算和比较大小的运算 这里不作介绍 只是对的乘号最佳插入方式进行探讨 假设s1 si 2 i n 中插入j个乘号 其中s1 sk中插入了j 1个乘号 即乘式中的第j 1项为sk 1 si j k i 1 分析 设ans i j 长度为i的数串中插入j个乘号的最大乘积 整型数组 显然ans i 0 s1 si对应的整型数组 ans i j max ans k j 1 sk 1 si 1 i n 1 j min i 1 m j k i 1 ans n m 即为其解 分析 由于乘式中第j 1项sk 1 si为常量 因此要使得ans i j 最大 则s1 sk中插入j 1个乘号的乘积必须最大 同样 为了寻找第j个乘号的最佳插入位置 必须一一查阅子问题ans j j 1 ans i 1 j 1 的解 显然该问题具备无后效性 最优子结构的特征 适用于动态规划方法 状态的确定 我们用ans i j 表示前i个字符插入j个乘号可以获得的最大值则有 ans i 0 s1 sians i j max ans k j 1 sk 1 si j k i 1 ans n m 即为其解 代码 输入n m和数串s fori 1tondoans i 0 s1 si对应的整数数组 fori 2tondo 阶段 枚举数串的长度 forj 1tomin i 1 m do 状态 枚举长度为i的数串中插入的乘号个数 fork jtoi 1do 决策 枚举第j个乘号的插入位置 beginnext sk 1 si对应的整数数组 计算第j 1项 ans i j max ans i j ans k j 1 next 计算状态转移方程 end for 输出最大乘积ans n m 过河 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中L是桥的长度 坐标为0的点表示桥的起点 坐标为L的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是S到T之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 分析 从正面来考虑的话 这个问题是一个搜索性的问题 需要考虑从当前点出发可以跳到的所有点 然而从反面考虑的话 我们只需要考虑那些能到用一步到达当前点的所有点中 踩到石头数最小的那个 即opt i min opt k max 0 i t k i s bri i 代码 Fori 1tondoopt i 10000000 opt 0 0 Fori stoL tdofork max 0 i t toi sdoif opt k bri i opt i opt i opt k bri i 以上都是线性动规的一些例题 它们的基础时间复杂度都是O N2 装箱问题 有一个箱子容量为maxv 正整数 maxv 20000 同时有n件物品 0 n 30 每件物品有一个体积vi 正整数 要求从这n件物品中任取若干件装入箱内 使箱子的剩余空间最小 分析 这是一个最基础的背包问题 只需要考虑选取哪几个物品放入箱子 可以使得剩余体积最小 这道题的基本做法当然还是穷举放进背包的物品编号 若我们把取该物品记为1 不取该物品记为0 那么使用某种放入方式将对应一个2进制串 因此这类问题也被称为0 1背包问题 如果我们不从物品角度考虑 而是从体积角度考虑的话 就会发现 这个问题还可以被描述为 w i 的体积是否能由这些物品得到 状态的确定 我们用opt i j 布尔 表示前i个物品是否能达到j体积 则opt i j 的值取决于前i 1个物品能否达到j体积 或者是前i 1个物品能否达到j v i 体积则有opt i j opt i 1 j v i or opt i 1 j 初值为opt 0 0 true 其他都为false 代码 memset opt 0 sizeof opt opt 0 0 1 for inti 1 i v i opt i j opt i 1 j opt i 1 j v i elseopt i j opt i 1 j 采药 辰辰是个天资聪颖的孩子 他的梦想是成为世界上最伟大的医师 为此 他想拜附近最有威望的医师为师 医师为了判断他的资质 给他出了一个难题 医师把他带到一个到处都是草药的山洞里对他说 孩子 这个山洞里有一些不同的草药 采每一株都需要一些时间 每一株也有它自身的价值 我会给你一段时间 在这段时间里 你可以采到一些草药 如果你是一个聪明的孩子 你应该可以让采到的草药的总价值最大 输入的第一行有两个整数T 1 T 1000 和N 1 N 100 用一个空格隔开 T代表总共能够用来采药的时间 N代表山洞里的草药的数目 接下来的N行每行包括两个在1到100之间 包括1和100 的整数 分别表示采摘某株草药的时间和这株草药的价值 分析 和上面一个问题一样 这个问题同样可以采用搜索解决 然而搜索的时间复杂度也同样相当的可怕 那我们可不可以借鉴一下上面的想法来解决这个问题呢 状态的确定 答案是肯定的 类似地 我们用opt i j 表示前i个物体在j时间内的一个参数 但是我们在里面存的值并不是能否达到 而是在这个状态下可以达到的最大价值 但是状态的转移方程稍微有些差别 除了考虑opt i 1 j t i 和opt i 1 j 之外 还要考虑opt i j 1 这样可以最后直接输出opt n maxt 从而省掉一次扫描 即opt i j 表示前i个物体在j时间内可以达到的最大价值 注意这里包括不足j时间的情况 代码 memset opt 0 sizeof opt opt 0 0 0 for inti 1 i v i opt i j max opt i 1 j opt i 1 j t i value i opt i j 1 elseopt i j max opt i 1 j opt i j 1 printf d n opt n maxt DairyQueen 奶牛Bassie去DQ打工 遇到一个客人给了一张好大面值的钞票 于是Bassie不得不为了给这位顾客找零而面对这样一个问题 现在店里一共有n种硬币 对这些不同种的硬币进行编号 编号为i的硬币面值为a i 因为奶牛的手指头是有限的 因此他只能向你求助啦 已知总需找零数为total 1 total 1000 1 n 1000 1 a i 300 求一共有多少种解决方案 输入 第一行为硬币总值total和硬币种类数n 以下n行为数值a i i 1 2 3 n 输出 一行 解决方案数 分析 这道题目和上面的采药的区别仅仅在于 每个物品可以无限次的取 当然 这样的问题仍然可以用背包模型来解决 我们将这种模型称为无限背包 在这种情况下 我们只要把opt i 1 j a i 改成opt i j a i 即允许一种物品被取多次 由于是计数 所以opt i j opt i j a i opt i 1 j 一个重要的优化 我们可以把opt数组压缩成长度为total的一维数组 因为这样是不会影响结果的 但可以大大降低它的空间复杂度 状态的确定 我们用opt j 表示硬币总面值为j时共有多少种方法opt j opt j opt j a i i 1 2 3 n 代码 memset opt 0 sizeof opt opt 0 1 for inti 1 i n i for intj a i j total j opt j opt j opt j a i printf d n opt total 多重背包 问题题目 有N种物品和一个容量为V的背包 第i种物品最多有m i 件可用 每件体积是v i 价值是w i 求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量 且价值总和最大 输入样例 1003 maxv n 704020 v1 v2 vn 504030 w1 w2 wn 123 m1 m2 m3 mn 分析 本题和无限背包问题很类似 基本的方程只需将无限背包问题的方程略微一改即可 因为对于第i种物品有m i 1种策略 取0件 取1件 取m i 件 令f i v 表示前i种物品恰放入一个容量为v的背包的最大价值 则 f i v max f i 1 v k v i k w i 0 k m i 时间复杂度是O V m i 另一种好想好写的基本方法是转化为0 1有限背包求解 把第i种物品换成m i 件该物品 即转化成了物品数为 m i 的0 1有限背包问题 直接求解 复杂度仍然是O V m i 但是我们期望将它转化为有限背包问题之后能够降低时间复杂度 分析 应用二进制的思想 我们考虑把第i种物品换成若干件物品 使得原问题中第i种物品可取的每种策略 取0 m i 件 均能等价于取若干件代换以后的物品 另外 取超过m i 件的策略必不能出现 方法是 将第i种物品分成若干件物品 其中每件物品有一个系数 这件物品的体积和价值均是原来的体积和价值乘以这个系数 使这些系数分别为1 2 4 2 k 1 m i 2 k 1 且k是满足m i 2 k 1 0的最大整数 例如 如果m i 为13 就将这种物品分成系数分别为1 2 4 6的四件物品 分成的这几件物品的系数和为m i 表明不可能取多于m i 件 另外这种方法也能保证对于0 m i 间的每一个整数 均可以用若干个系数的和表示 这样就将第i种物品分成了 logm i 种物品 将原问题转化为了复杂度为O V logm i 的有限背包问题 是很大的改进 k 0 转化后物品的个数for inti 1 i0 if m i t k v1 k v i t w1 k w i t m i m i t t 1 else k v1 k v i m i w1 k w i m i m i 0 代码 for inti 1 i v i j if opt j v1 i w1 i opt j opt j opt j v1 i w1 i if opt j best best opt j printf d n best 代码 以上都是背包问题的一些例题 他们的基础时间复杂度都是O mn 的 最小代价子母树 问题描述 有n堆沙子排成一排 每堆沙子有一个数量 例如任意2堆相邻的沙子可以进行合并 将两堆沙子合并为一堆时 两堆沙子数量的和称为合并这两堆沙子的代价 经过不断的归并 最后将这些沙子归为一堆 而全部归并代价的和称为总代价 例如上列数 其中2种归并方案的代价为 第1种的总代价为20 24 25 44 69 87 267第2种的总代价为15 37 22 28 59 87 248由此可见 不同的归并过程得到的总代价是不一样的 问题 当n个数给出后 找出一种合理的归并方法 使得总代价最小 分析 1 如果把归并1 4堆看成整个问题 则这个问题可以分解为三个归并方案 每个归并方案包含1 2个子问题 先归并1 3 再与4归并 归并1 2 归并3 4 再归并 归并2 4 再与1归并 2 如果我们继续分析增加更多堆数进行归并的问题 就会发现n个数归并时 会分解为n 1种类型 Case1 归并第1堆 归并2 n堆 再最后归并Case2 归并1 2堆 归并3 n堆 再最后归并 Casen 1 归并1 n 1堆 归并第n堆 再最后归并 分析 通过前面的分析 我们看到 归并代价实际上由两部分组成 1 归并树左右子树的最小代价之和 2 归并树所有叶结点的权值之和而对于opt数组中的子区间数值的取值大小 我们有两种渠道来获取 1 利用普通的dp 枚举开始结点和区间长度来进行DP 2 记忆化搜索 状态的确定 我们用opt i j 表示i j区间合并成一堆的最小代价 则有上面的结论有opt i j min opt i k opt k 1 j k i j 1 value i j opt i i value i 代码 for inti 1 iopt i k opt k 1 i j 1 v i j 1 v i 1 opt i i j 1 opt i k opt k 1 i j 1 v i j 1 v i 1 printf d n opt 1 n Power 多瑞卡得到了一份有趣而高薪的工作 每天早晨他必须关掉他所在村庄的街灯 所有的街灯都被设置在一条直路的同一侧 多瑞卡每晚到早晨5点钟都在晚会上 然后他开始关灯 开始时 他站在某一盏路灯的旁边 每盏灯都有一个给定功率的电灯泡 因为多端卡有着自觉的节能意识 他希望在耗能总数最少的情况下将所有的灯关掉 多端卡因为太累了 所以只能以1m s的速度行走 关灯不需要花费额外的时间 因为当他通过时就能将灯关掉 编写程序 计算在给定路灯位置 灯泡功率以及多瑞卡的起始位置的情况下关掉所有的灯的最少耗能 Power 输入第一行包含一个整数N 2 N 1000 表示该村庄路灯的数量 第二行包含一个整数V 1 V N 表示多瑞卡开始关灯的路灯号码 接下来的N行中 每行包含两个用空格隔开的整数D和W 用来描述每盏灯的参数 其中0 D W 1000 D表示该路灯与村庄开始处的距离 用米为单位来表示 W表示灯泡的功率 每秒种该灯泡所消耗的能量数 路灯是按顺序给定的 输出一行 包含一个整数 即消耗能量之和的最小值 注意结果不超过1 000 000 000 分析 首先 我们必须明确这样一个决策 我们关掉的灯必然是一个连续的区间 也就是说 我们在路过的时候肯定会把灯顺手关掉 不然肯定不是最优解 而在关掉一个区间之后 我们需要作出的决定就是 回头关另外一边的灯还是继续朝当前方向走关前面的灯 对于我们的最后求解区间i j 有2种可能 最后关第j盏灯 或者最后关第i盏灯 分析 为了实现对这两种情况的记录 我们需要两个数组 分别存放关完 i j 区间的所有路灯后分别站在两个端点时最小的电能消耗值 并且这两个数组中 k gdje k 1 2 3 gdje 1 区间的数值和 gdje k k gdje 1 n 区间的数值都是很容易确定的 gdje为开始位置 在下面的动规过程中 我们只需要决策是需要转向另外一边还是继续走下去就可以了 状态的确定 我们用left i j 表示关完灯后人站在i点所消耗的最小电能 用right i j 表示关完灯后人站在j点所消耗的最小电能 则有left i j min left i l j value 1 i value j 1 n pos i 1 pos i right i l j value 1 i value j 1 n pos j pos i right i j min left i j 1 value 1 i 1 value j n pos j pos i right i j 1 value 1 i 1 value j n pos j pos j 1 加分二叉树 设一个n个节点的二叉树tree的中序遍历为 l 2 3 n 其中数字1 2 3 n为节点编号 每个节点都有一个分数 均为正整数 记第i个节点的分数为di tree及它的每个子树都有一个加分 任一棵子树subtree 也包含tree本身 的加分计算方法如下 subtree的左子树的加分 subtree的右子树的加分 subtree的根的分数若某个子树为空 规定其加分为1 叶子的加分就是叶节点本身的分数 不考虑它的空子树 试求一棵符合中序遍历为 1 2 3 n 且加分最高的二叉树tree 要求输出 1 tree的最高加分 2 tree的前序遍历 加分二叉树 输入格式 第1行 一个整数n n 30 为节点个数 第2行 n个用空格隔开的整数 为每个节点的分数 分数 100 输出格式 第1行 一个整数 为最高加分 结果不会超过4 000 000 000 第2行 n个用空格隔开的整数 为该树的前序遍历 输入样例 5571210输出样例14531245 分析 我们可以发现这道题目给我们提供了一段序列 我们需要做的就是每次选取一个断开的点 然后把问题递归地求解就可以了 这就为我们的动规提供了条件 具有最优子结构性质 我们需要做出的决策 仅仅是从当前序列中选取一个点作为当前子树的根节点 所以动规的转移是O n 的 状态的确定 我们用opt i j 表示在 i j 区间内可以获得的最大加分 用root i j 表示 i j 范围内选取哪个结点作为根时可以获得最大加分 对区间 i j i j 我们定义opt i j 1 则有 opt i j max opt i k 1 opt k 1 j value k k i i 1 i 2 j root i j 为对应的k值 intsearch intl intr if opt l r 0 returnopt l r for inti l iopt l r opt l r search l i 1 search i 1 r value i root l r i memset opt 0 sizeof opt for inti 1 i n 1 i opt i i 1 1 for inti 1 i n i opt i i value i intAns search 1 n 代码 上面几道题是区间动态规划的一些例题 它们的基础时间复杂度都是O N3 的 聚会的快乐 Party 你要组织一个由你公司的人参加的聚会 你希望聚会非常愉快 尽可能多地找些有趣的人 但是劝你不要同时邀请某个人和他的上司 因为这可能带来争吵 给定N个人 姓名 他幽默的系数 以及他上司的名字 找到能使幽默系数和最大的若干个人 输入第一行一个整数N N 100 接下来有N行 每一行描述一个人 信息之间用空格隔开 姓名是长度不超过20的字符串 幽默系数是在0到100之间的整数输出邀请的人最大的幽默系数和 分析 仔细看过这个问题之后 会发现这道题目和我们上面遇到的一些类型的动态规划都有点区别 它的数据并不是以线性或者表格的形式 而是以树的形式进行存储的 可以发现 这道题目中的关系可以简单地描述为 在一棵树中 父亲结点和儿子结点不可以同时选取 而每个结点有一个权值 在满足上述条件的情况下求出可以选取出的最大值 这就是我们所说的树形动态规划 由于树本身的递归性质 我们使用记忆化搜索的方法来完成子问题答案的存储 状态的确定 显然 对于每个结点我们需要记录当前结点是否被取到 以及在该种情况下该子树所能获得的最大幽默系数 因此 我们定义opt 1 i 表示在编号为i的结点必取的情况下以i为根的子树所能获得的最大快乐值 相应地 opt 0 i 表示在编号为i的结点不取的情况下以i为根的子树所能获得的最大幽默系数 则根据题目中的要求 我们有opt 1 i value i opt 0 k k为所有i的子结点的编号 opt 0 i max opt 0 k opt 1 k k为所有i的子结点的编号 w数组用来存储边 r i 存放编号为i的结点的儿子数 d i 中存放编号为i的结点的在w数组中最后一条边的编号 其中d 0 0 d i d i 1 r i intsearch intflag intlab 记忆化搜索if opt flag lab 0 returnopt flag lab intp flag 1 value lab 0 for inti d lab 1 i d lab i if flag 1 p search 0 w i elsep max search 0 w i search 1 w i opt flag lab p returnp memset d 0 sizeof d for inti 1 i n i d i d i 1 r i ans max search 1 root search 0 root 代码 二 苹果树 有一棵苹果树 如果树枝有分叉 一定是分2叉 就是说没有只有1个儿子的结点 这棵树共有N个结点 叶子点或者树枝分叉点 编号为1 N 树根编号一定是1 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置 下面是一颗有4个树枝的树现在这颗树枝条太多了 需要剪枝 但是一些树枝上长有苹果 给定需要保留的树枝数量 求出最多能留住多少苹果 二 苹果树 输入格式第1行2个数 N和Q 1 Q N 1 N 100 N表示树的结点数 Q表示要保留的树枝数量 接下来N 1行描述树枝的信息 每行3个整数 前两个是它连接的结点的编号 第3个数是这根树枝上苹果的数量 每根树枝上的苹果不超过30000个 输出格式一个数 最多能留住的苹果的数量 分析 同样 这道题目给出的数据是以树形结构连接的 而且这道题很明确的告诉我们 每个结点只可能是叶节点或者拥有两个儿子 因此 我们可以讨论每个结点伸出的两个树枝的剪枝情况 并且仍然用记忆化搜索完成 状态的确定 我们用opt i j 表示编号为i的结点作为根的子树中保留j个树枝可以获得的最大苹果数 状态转移方程为 opt i j maxopt i rc j 1 value i rc 剪掉左枝 opt i lc j 1 value i lc 剪掉右枝 max opt i lc k opt i rc j 2 k value i lc value i rc 0 k j 2 左枝和右枝都不剪 intsearch intlab intnum if opt lab num 0 returnopt lab num if lc lab 0 num 0 return0 intl lc lab r rc lab if search r num 1 value r opt lab num opt lab num opt r num 1 value r if search l num 1 value l opt lab num opt lab num opt l num 1 value i for inti 0 iopt lab num opt lab num opt l i opt r num 2 i value l value r returnopt lab nu