noip动态规划讲解.ppt

历届NOIp动态规划讲解 动态规划 dynamicprogramming 是运筹学的一个分支 是求解决策过程最优化的数学方法 动态规划算法把多阶段过程转化为一系列单阶段问题 利用各阶段之间的关系 逐个求解 以得到全局最优策略 动态规划是信息学竞赛中选手必须熟练掌握的一种算法 它以其多元性广受出题者的喜爱 近年来 动态规划几乎每次都出现在NOIp的赛场上 而且还有越来越多的趋势 因此 掌握基本的NOIp动态规划题是至关重要的 动态规划实质 枚举 递推 状态 状态转移方程 SampleProblem1 1 3 5 9 1 从树的根到树的叶节点 最多能取多少数 贪心 答案错误 暴力搜索 如果数据大会超时 动态规划 我们先将NOIp里的动态规划分分类 最长不降子序列背包方格取数石子归并状态压缩数学递推顺序递推 最长不降子序列 设有由n个不相同的整数组成的数列 记为 a 1 a 2 a n 且a i a j i j n 例如3 18 7 14 10 12 23 41 16 24 若存在i1 i2 i3 ie且有a i1 a i2 a ie 则称为长度为e的不下降序列 如上例中3 18 23 24就是一个长度为4的不下降序列 同时也有3 7 10 12 16 24长度为6的不下降序列 最长的不下降序列就是求长度最长的子序列 Fori 1TonDoForj 1Toi 1DoIf a i a j And f i f j 1 Thenf i f j 1 合唱队形 NOIp2004 问题描述 N位同学站成一排 音乐老师要请其中的 N K 位同学出列 使得剩下的K位同学排成合唱队形 合唱队形是指这样的一种队形 设K位同学从左到右依次编号为1 2 K 他们的身高分别为T1 T2 TK 则他们的身高满足T1Ti 1 TK 1 i K 你的任务是 已知所有N位同学的身高 计算最少需要几位同学出列 可以使得剩下的同学排成合唱队形 输入文件 输入文件第一行是一个整数N 2 N 100 表示同学的总数 第一行有n个整数 用空格分隔 第i个整数Ti 130 Ti 230 是第i位同学的身高 输出文件 输出文件包括一行 这一行只包含一个整数 就是最少需要几位同学出列 SampleProblem2 最长不降子序列 最长不降子序列 最长不降子序列 最长不降子序列 依此类推 最长不降子序列 拦截导弹 NOIp1999 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度数据是不大于30000的正整数 计算这套系统最多能拦截多少导弹 如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 样例 INPUTOUTPUT389207155300299170158656 最多能拦截的导弹数 2 要拦截所有导弹最少要配备的系统数 SampleProblem3 最长不降子序列 第一问 最长下降子序列 第二问 DP 反例 987110654 最长不降子序列 987110654 DP 987110654 110 110 10 10 3次 最长不降子序列 987110654 贪心 2次 987110654 10654 DP不是万能的 10654 背包 01背包 有N件物品和一个容量为V的背包 第i件物品的费用是c i 价值是w i 求解将哪些物品装入背包可使价值总和最大 完全背包 有N种物品和一个容量为V的背包 每种物品都有无限件可用 第i种物品的费用是c i 价值是w i 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量 且价值总和最大 Fori 1TonDoForj MaxDowntoa i Do a i ToMax Iff j f j a i b i Thenf j f j a i b i 背包 SampleProblem4 金明的预算方案 NOIp2006 问题描述 金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间金明自己专用的很宽敞的房间 更让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过N元钱就行 今天一早 金明就开始做预算了 他把想买的物品分为两类 主件与附件 附件是从属于某个主件的 如果要买归类为附件的物品 必须先买该附件所属的主件 每个主件可以有0个 1个或2个附件 附件不再有从属于自己的附件 金明想买的东西很多 肯定会超过妈妈限定的N元 于是 他把每件物品规定了一个重要度 分为5等 用整数1 5表示 第5等最重要 他还从因特网上查到了每件物品的价格 都是10元的整数倍 他希望在不超过N元 可以等于N元 的前提下 使每件物品的价格与重要度的乘积的总和最大 设第j件物品的价格为v j 重要度为w j 共选中了k件物品 编号依次为j1 j2 jk 则所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 背包 SampleProblem4 输入文件 第1行 为两个正整数Nm 其中N 0 表示该物品为附件 q是所属主件的编号 输出文件 只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 输入样例 100058002040051300514003050020 输出样例 2200 背包 Fori 1TonDoForj mDowntoa i DoIff j a i 1thenBegin00Iff j a i b i f j Thenf j f j a i b i Ff f j a i b i 01Ifj s i 1 1 f j s i 1 1 Thenf j s i 1 1 Ff s i 1 2 10Ifj s i 2 1 f j s i 2 1 Thenf j s i 2 1 Ff s i 2 2 11Ifj s i 1 1 s i 2 1 f j s i 1 1 s i 2 1 Thenf j s i 1 1 s i 2 1 Ff s i 1 2 s i 2 2 End End 背包 SampleProblem5 邮票面值设计 NOIp1999 给定一个信封 最多只允许粘贴N张邮票 计算在给定K N K 40 种邮票的情况下 假定所有的邮票数量都足够 如何设计邮票的面值 能得到最大值MAX 使在1 MAX之间的每一个邮资值都能得到 例如 N 3 K 2 如果面值分别为1分 4分 则在1分 6分之间的每一个邮资值都能得到 当然还有8分 9分和12分 如果面值分别为1分 3分 则在1分 7分之间的每一个邮资值都能得到 可以验证当N 3 K 2时 7分就是可以得到的连续的邮资最大值 所以MAX 7 面值分别为1分 3分 样例 INPUTN 3K 2OUTPUT13MAX 7 背包 如果你一看到这道题目就想到搜索 那么 恭喜你 你答对了 方格取数 SampleProblem6 方格取数 NOIp2000 设有N N的方格图 N 10 我们将其中的某些方格中填入正整数 而其他的方格中则放入数字0 如下图所示某人从图的左上角的A点出发 可以向下行走 也可以向右走 直到到达右下角的B点 在走过的路上 他可以取走方格中的数 取走后的方格中将变为数字0 此人从A点到B点共走两次 试找出2条这样的路径 使得取得的数之和为最大 方格取数 13 14 4 21 15 67 方格取数 一取方格数 f i j max f i 1 j f i j 1 现在要做的数二取方格数 是否还能像一取方格数那样如法炮制呢 答案是肯定的 我们观察一下它的路径 f i j 是从f i 1 j 或者f i j 1 走来 无论是从f i 1 j 还是f i j 1 走来 要么是x坐标 1 要么是y坐标 1 总归x坐标的值 y坐标的值一定比前一个多1 我们来验证一下 方格取数 X坐标 3 3 3 3 6Y坐标 3 4 3 4 7Z坐标 4 4 4 4 8 方格取数 再观察 我们发现 走第n步时 能走到点是固定的 观察其坐标我们发现 第n步能走到的点其坐标和为n 1 因此 走到第n步时 x坐标和y坐标的和就知道 n 1 这样我们就不必同时知道2条路线x坐标和y坐标了 知道其中一个t 另外一个就可以用n 1 t来表示了 于是此题迎刃而解 方格取数 用f x i j 表示走到第x步时 第1条路线走到横坐标为i的地方 第2条路线走到了横坐标为j的地方 这样 我们只要枚举x i j 就能递推出来了 Forx 3Tom nDoFori 1ToMin x n DoForj 1ToMin x n DoBeginf x i j Max f x 1 i j f x 1 i 1 j f x 1 i j 1 f x 1 i 1 j 1 Ifi jThenInc f x i j a i x i ElseBeginInc f x i j a x i i Inc f x i j a x j j End End 同样三取方格数只要f x i j k 用同样的方法即可 方格取数 传纸条 NOIp2008 问题描述 小渊和小轩是好朋友也是同班同学 他们在一起总有谈不完的话题 一次素质拓展活动中 班上同学安排做成一个m行n列的矩阵 而小渊和小轩被安排在矩阵对角线的两端 因此 他们就无法直接交谈了 幸运的是 他们可以通过传纸条来进行交流 纸条要经由许多同学传到对方手里 小渊坐在矩阵的左上角 坐标 1 1 小轩坐在矩阵的右下角 坐标 m n 从小渊传到小轩的纸条只可以向下或者向右传递 从小轩传给小渊的纸条只可以向上或者向左传递 在活动进行中 小渊希望给小轩传递一张纸条 同时希望小轩给他回复 班里每个同学都可以帮他们传递 但只会帮他们一次 也就是说如果此人在小渊递给小轩纸条的时候帮忙 那么在小轩递给小渊的时候就不会再帮忙 反之亦然 还有一件事情需要注意 全班每个同学愿意帮忙的好感度有高有低 注意 小渊和小轩的好心程度没有定义 输入时用0表示 可以用一个0 100的自然数来表示 数越大表示越好心 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条 即找到来回两条传递路径 使得这两条路径上同学的好心程度只和最大 现在 请你帮助小渊和小轩找到这样的两条路径 SampleProblem7 石子归并 SampleProblem8 石子归并原题 题目描述 在一个圆形操场的四周摆放着N堆石子 N 100 现要将石子有次序地合并成一堆 规定每次只能选取相邻的两堆合并成新的一堆 并将新的一堆的石子数 记为该次合并的得分 编一程序 由文件读入堆栈数N及每堆栈的石子数 20 选择一种合并石子的方案 使用权得做N 1次合并 得分的总和最小 输入数据 第一行为石子堆数N 第二行为每堆的石子数 每两个数之间用一个空格分隔 输出数据 一行 最小总和 输入 44594 输出 22 石子归并 4 5 9 4 石子归并 我们用f i j 表示以i堆石子为开头 以j堆石子为结尾的一系列石子归并起来的最小总和 因为题目中说 只能归并相邻的两堆石子 所以 f i j 这一系列石子必然由f i k 和f k 1 j i k j 这两堆石子归并而来 只要在所有的f i k f k 1 j 中取个最小值 就是原来此次没归并前的最小值 加上自己本身所有石子的和 因为归并一次的代价是所有石子的总和 就是我们要求的f i j 因此 状态转移方程为 而f i i 和一段石子的总和是可以预处理的 只要将石子序列倍长 复杂度O n 3 此题就能顺利AC了 石子归并 Fori 1Ton 1DoForj 1To2 n iDoBeginf j j i Maxlongint Fork jToj iDoIff j j i f j k f k 1 j i Thenf j j i f j k f k 1 j i f j j i f j j i Sum j j i End 这样 求归并的最大值也是同样的方法 不再赘述 石子归并 SampleProblem9 能量项链 NOIp2006 在Mars星球上 每个Mars人都随身佩带着一串能量项链 在项链上有N颗能量珠 能量珠是一颗有头标记与尾标记的珠子 这些标记对应着某个正整数 并且 对于相邻的两颗珠子 前一颗珠子的尾标记一定等于后一颗珠子的头标记 因为只有这样 通过吸盘 吸盘是Mars人吸收能量的一种器官 的作用 这两颗珠子才能聚合成一颗珠子 同时释放出可以被吸盘吸收的能量 如果前一颗能量珠的头标记为m 尾标记为r 后一颗能量珠的头标记为r 尾标记为n 则聚合后释放的能量为 Mars单位 新产生的珠子的头标记为m 尾标记为n 需要时 Mars人就用吸盘夹住相邻的两颗珠子 通过聚合得到能量 直到项链上只剩下一颗珠子为止 显然 不同的聚合顺序得到的总能量是不同的 请你设计一个聚合顺序 使一串项链释放出的总能量最大 例如 设N 4 4颗珠子的头标记与尾标记依次为 2 3 3 5 5 10 10 2 我们用记号 表示两颗珠子的聚合操作 j k 表示第j k两颗珠子聚合后所释放的能量 则第4 1两颗珠子聚合后释放的能量为 4 1 10 2 3 60 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 4 1 2 3 10 2 3 10 3 5 10 5 10 710 石子归并 SampleProblem10 乘积最大 NOIp2000 问题描述 设有一个长度为N的数字串 要求选手使用K个乘号将它分成K 1个部分 找出一种分法 使得这K 1个部分的乘积能够为最大 输入 程序的输入共有两行 第一行共有2个自然数N K 6 N 40 1 K 6 第二行是一个长度为N的数字串 输出 输出所求得的最大乘积 一个自然数 样例输入 421231 样例输出 62 石子归并 这道题目要求把一个长度为n的数字串分成k段 使得每段的乘积最大 通过刚才的石子归并思想 我们可以用f i j 表示前i个数字我分了j段所能得到的最大值 那么f i j 就可以从f k j 1 前k个数字分成了j 1段 推来 因为f i j 就是f k j 1 和 k 1 i 这段数字串的乘积 于是状态转移方程即可得出 f i j Max f k j 1 Number k 1 i j 1 k i 其中Number k 1 j 表示数字串从第k 1位到第i位转换成数字的值 对于题目中所说的具有很强枚举意味的变量 如k段 n次等 一般将其放入状态中枚举 而诸如最大值最小值之类的变量 一般放入数组中作为值递推 SampleProblem11 统计单词个数 NOIp2001 问题描述 给出一个长度不超过200的由小写英文字母组成的字母串 约定 该字串以每行20个字母的方式输入 且保证每行一定为20个 要求将此字母串分成k份 1 k 40 且每份中包含的单词个数加起来总数最大 每份中包含的单词可以部分重叠 当选用一个单词之后 其第一个字母不能再用 例如字符串this中可包含this和is 选用this之后就不能包含th 单词在给出的一个不超过6个单词的字典中 要求输出最大的个数 样例输入 3thisisabookyouareaoh4isaoksab 样例输出 7this isabookyoua reaoh 石子归并 石子归并 看到这道题目应该马上有这种意识了 和乘积最大神似 所以本题除了求出i j之间有多少单词以外基本上就没什么难度了 预处理出i j之间有多少单词 其实也可以用DP 首先 题目告诉我们 如果a是b的前缀 那么b肯定没用了 为什么 所以第一步删串 之后的任务就是求单词数了 令s i j 表示i j之间有多少个单词 那么s i j s i j 1 以第j位为结尾 包含在i j这段串里的单词个数 如串cabce 单词有cab abc 明显第1 3之间有1个单词 而1 4之间呢 1 3有的它肯定也有 再去枚举单词中有没有是cabc后缀的单词 最终f 1 4 f 1 3 1 SampleProblem12 矩阵取数游戏 NOIp2007 问题描述 帅帅经常更同学玩一个矩阵取数游戏 对于一个给定的n m的矩阵 矩阵中的每个元素aij据为非负整数 游戏规则如下 1 每次取数时须从每行各取走一个元素 共n个 m次后取完矩阵所有元素 2 每次取走的各个元素只能是该元素所在行的行首或行尾 3 每次取数都有一个得分值 为每行取数的得分之和 每行取数的得分 被取走的元素值 2i 其中i表示第i次取数 从1开始编号 4 游戏结束总得分为m次取数得分之和 帅帅想请你帮忙写个程序 对于任意矩阵 可以求出取数后的最大得分 输入 第一行为两个用空格隔开的整数n和m 第2 n 1行为n m矩阵 其中每行有m个用单个空格隔开 输出 一个整数 即输入矩阵取数后的最大的分 限制 60 的数据满足 1 n m 30 答案不超过10 6100 的数据满足 1 n m 80 0 aij 1000 石子归并 改变一下题目的叙述 每行有m个数 倒数第i次取的得分是a i 2 m 1 i 倒推 因为每次只能取一段中的头或尾 所以剩下的永远是连续的一段 每次加入头或尾 把一段的头和尾看做一堆石子 把a i 2 m 1 i 看做每次归并的加分 每次归并不是取相邻的 而是取一段中的头或尾 就是石子归并 用f i j k 表示第i行 取了一些数后剩下连续的一段从j到k 那么状态转移方程就很好写了 f i j k Max f i j 1 k a j 1 2 m k j 1 f i j k 1 a k 1 2 m k j 1 这道题目还要高精度 建议写好非高精的DP再修改成高精度的 石子归并 状态压缩 过河 NOIp2005 问题描述 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中L是桥的长度 坐标为0的点表示桥的起点 坐标为L的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是S到T之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 输入文件 第一行一个正整数L 1 L 10 9 表示独木桥的长度 第二行有三个正整数S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中1 S T 10 1 M 100 第三行有M个不同的正整数分别表示这M个石子在数轴上的位置 数据保证桥的起点和终点处没有石子 所有相邻的整数之间用一个空格隔开 输出文件 一个整数 表示青蛙过河最少需要踩到的石子数 SampleProblem13 状态压缩 此题乍一看上去好像很简单 因为只要沿着青蛙跳的方向 逐步递推即可 大致代码如下 Fori 1ToL t 1Do 仔细想想为什么 Forj sTotDoIfi这个位子有石头ThenIff i f i j 1Thenf i f i j 1ElseIff i f i j Thenf i f i j 但是有个地方我们忽略了 那就是数据规模 L最大有10 9 第一个For就已经无法承受庞大的时间限制和空间限制了 所以 这种方法需要进行改进 而改进的方法 就是状态压缩 状态压缩 我们可以发现题目的一个玄机 虽然L很大 但是M却很小 也就是说 石子很稀疏 石子稀疏对我们解题有什么帮助呢 我们来看一下下面的推断 第一种情况 当s t时 很简单 青蛙踩到的石头肯定是s的倍数 那么只要统计一下所有石子中有多少是s的倍数 输出即可 第二种情况 s t我们先来看一组数据 s 4 t 5 从数据中我们看到 12以后的点全部都是可以到达的了 如果s 4 t 5 在一段100000的距离中没有石头 其实12以后的点都是不用递推就知道肯定能到达的 那么我们用原始的方法做就会浪费很大的资源 所以当s 4 t 5时 如果一段没有石头的区间长度在4 5 20以外 那么我们只要递推前20就可以了 因为20后面的情况是一样的 仔细想想为什么 状态压缩 假设s 3 t 5 那么11 3 4 4就也可以到达了 所以 只有当t s 1时 连续的点的起始位置才能尽量后面 最坏情况就是s 9 t 10了 仔细想想为什么 跟前面的s 4 t 5的情况一样 其实s 9 t 10时只要一段没有石头的区间长度在90之外 我们都把它当做90对待就可以了 因此 我们每次对于一段没有石头的区间长度为x 如果xt t 1 时 我们就把它当做t t 1 处理 这样 最大的复杂度就是t t 1 石头个数 1 90 101 9090 比之前的复杂度大大降低 这种方法叫状态压缩 我们这题用的方法叫离散化 至此 过河完美AC 状态压缩 SampleProblem14 数的划分 NOIp2001 问题描述 将整数n分成k份 且每份不能为空 任意两份不能相同 不考虑顺序 例如 n 7 k 3 下面三种分法被认为是相同的 1 1 5 1 5 1 5 1 1 问有多少种不同的分法 输入 n k 6 n 200 2 k 6 输出 一个整数 即不同的分法 样例 输入 73输出 4 四种分法为 1 1 5 1 2 4 1 3 3 2 2 3 数学递推 应该明确这是一道数学题 数学题往往有明显或暗藏的规律可以快速求得解 在NOIp中数学递推题并不常见 但不能排除它出现的可能性 对于这类问题 我们不能盲目找规律 而要细细寻找每个状态之间的内在联系 从而一步一步求得最终要求的答案 此类问题一般要用到数学公式 数学证明 方程变形 极端化等思想 根据题目的不同适当选取方法 根据前面讲的 有几个枚举量我们就设几个状态 这道题目明显n和k都是枚举量 要求的几种方案是值 因此建立起递推状态 f i j 表示将i分成j份的方案数 接下来就是写出状态转移方程了 一旦状态转移方程写出 那么f i j 就可以由f x y 等其他状态得来 因为得到最后我们要求得f n k 数学递推 数学递推 我们先来看一下f 10 4 的几种分割方法 如图 可以看见10 1 1 3 5 1 2 3 4 2 2 3 3 乍一看我们没发现什么规律 但是这些分割方法都有一个共同点 每种分割方法所分割出来的小整数都 1 因为不允许出现10 0 10这种分割 所以 数学递推 有了这个性质 我们来尝试下面的操作 将所有小整数都减去1 这样 f 10 4 就被改成了f 6 2 f 6 3 f 6 4 等小状态 通过类推 小状态可以分成更小的状态 一般地 f i j 就可以分成f i j 1 f i j 2 f i j 3 等小状态 而f i j 的种数就是小状态的总合 f i j f i j 1 f i j 2 f i j 3 f i j j 1 f i j j 数学递推 知道了递推公式 我们就可以推得f n k Fori 1TonDoForj 1TokDoIfi jThenFort 1TojDof i j f i j f i j t 时间复杂度是你n k 2的 虽然可以轻松过这题 但如果n 50000 k 200 这样的方法就超时了 所以我们要精益求精 这题还有O n k 的方法 观察下面的变形 f i j f i j 1 f i j 2 f i j j 数学递推 f i 1 j 1 f i 1 j 1 1 f i 1 j 1 2 f i 1 j 1 j 1 f i j 1 f i j 2 f i j j 1 f i j f i j 1 f i j 2 f i j j 1 f i j j f i 1 j 1 f i j j 这样 递推就成了n k的了 Fori 1TonDoForj 1TokDoIfi jThenf i j f i 1 j 1 f i j j 最后加点预处理 此题完美就AC了 反思 解决此类题目 必先学好数学 SampleProblem15 加分二叉树 NOIp2003 问题描述 设一个n个节点的二叉树tree的中序遍历为 l 2 3 n 其中数字1 2 3 n为节点编号 每个节点都有一个分数 均为正整数 记第j个节点的分数为di tree及它的每个子树都有一个加分 任一棵子树subtree 也包含tree本身 的加分计算方法如下 subtree的左子树的加分 subtree的右子树的加分 subtree的根的分数若某个子树为主 规定其加分为1 叶子的加分就是叶节点本身的分数 不考虑它的空子树 试求一棵符合中序遍历为 1 2 3 n 且加分最高的二叉树tree 要求输出 1 tree的最高加分 2 tree的前序遍历 输入格式 第1行 一个整数n n 30 为节点个数 第2行 n个用空格隔开的整数 为每个节点的分数 分数 100 顺序递推 因为此题给我们的是中序遍历 所以如果a i 为根 那么a 1 a i 1 就是这棵树的左子树 a i 1 a n 就是这棵树的右子树 同样的如果j是a 1 a i 1 这棵子树的根 那么a 1 a j 1 就是左子树中的左子树 a j 1 a i 1 就是左子树中的右子树 依次类推 这样 我们只要枚举i j这个区间和枚举这个区间的根k就可以了 至于路径 记录一下就可以了 Fori 1Ton 1DoForj 1Ton iDoFork jToj iDoIff j k 1 f k 1 j i a k f j j i Thenf j j i f j k 1 f k 1 j i a k 顺序递推 总结 动态规划是NOIp中的一类大问题 它在联赛中考的几率是99 动态规划的核心就是 状态 和 状态转移方程 有了这两样东西 或许还要再加点DFS 贪心 状态压缩 单调队列等来优化动态规划 基本上就可以放心DP了 1 在处理问题的过程中 要考虑全面 思索深入 抓准题目中的信息 适当进行筛选 作出合理的决策 3 平时多积累 要熟悉各种动态规划类型及其变种 如Floyd等 还要全面了解其他算法来辅助 2 认清动态规划本质 别把最长不降子序列当成背包来做 把石子归并当成数学问题来做 附录 相关练习题目最长不降子序列 p1061背包 p1025p1057p1104p1133p1198p1222p1334方格取数 p1143p1280p1364p1121石子归并 p1218p1455数学递推 p1073p1136p1210顺序递推 p1006p1011p1014p1063p1139p1232p1235p1292p1623树形动态规划 p1144p1180限定数目 p1037p1331p1386数据结构优化 p1404p1617其他 p1335p1431p1485