动态规划基础
本页面主要介绍了动态规划的基本思想,以及动态规划中状态及状态转移方程的设计思路,帮助各位初学者对动态规划有一个初步的了解。
本部分的其他页面,将介绍各种类型问题中动态规划模型的建立方法,以及一些动态规划的优化技巧。
引入
[IOI1994] 数字三角形
给定一个
1 2 3 4 5 |
|
在上面这个例子中,最优路径是
最简单粗暴的思路是尝试所有的路径。因为路径条数是
注意到这样一个事实,一条最优的路径,它的每一步决策都是最优的。
以例题里提到的最优路径为例,只考虑前四步
而对于每一个点,它的下一步决策只有两种:往左下角或者往右下角(如果存在)。因此只需要记录当前点的最大权值,用这个最大权值执行下一步决策,来更新后续点的最大权值。
这样做还有一个好处:我们成功缩小了问题的规模,将一个问题分成了多个规模更小的问题。要想得到从顶端到第
这时候还存在一个问题:子问题间重叠的部分会有很多,同一个子问题可能会被重复访问多次,效率还是不高。解决这个问题的方法是把每个子问题的解存储下来,通过记忆化的方式限制访问顺序,确保每个子问题只被访问一次。
上面就是动态规划的一些基本思路。下面将会更系统地介绍动态规划的思想。
动态规划原理
能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。
最优子结构
具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。
- 证明问题最优解的第一个组成部分是做出一个选择;
- 对于一个给定问题,在其可能的第一步选择中,假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择;
- 给定可获得的最优解的选择后,确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间;
- 证明作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解。方法是反证法,考虑加入某个子问题的解不是其自身的最优解,那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解,从而得到原问题的一个更优的解,从而与原问题最优解的假设矛盾。
要保持子问题空间尽量简单,只在必要时扩展。
最优子结构的不同体现在两个方面:
- 原问题的最优解中涉及多少个子问题;
- 确定最优解使用哪些子问题时,需要考察多少种选择。
子问题图中每个定点对应一个子问题,而需要考察的选择对应关联至子问题顶点的边。
无后效性
已经求解的子问题,不会再受到后续决策的影响。
子问题重叠
如果有大量的重叠子问题,我们可以用空间将这些子问题的解存储下来,避免重复求解相同的子问题,从而提升效率。
基本思路
对于一个能用动态规划解决的问题,一般采用如下思路解决:
- 将原问题划分为若干 阶段,每个阶段对应若干个子问题,提取这些子问题的特征(称之为 状态);
- 寻找每一个状态的可能 决策,或者说是各状态间的相互转移方式(用数学的语言描述就是 状态转移方程)。
- 按顺序求解每一个阶段的问题。
如果用图论的思想理解,我们建立一个 有向无环图,每个状态对应图上一个节点,决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长(短)路的问题(参见:DAG 上的 DP)。
最长公共子序列
最长公共子序列问题
给定一个长度为
子序列的定义可以参考 子序列。一个简要的例子:字符串 abcde
与字符串 acde
的公共子序列有 a
、c
、d
、e
、ac
、ad
、ae
、cd
、ce
、de
、ade
、ace
、cde
、acde
,最长公共子序列的长度是 4。
设
对于每个
可参考 SourceForge 的 LCS 交互网页 来更好地理解 LCS 的实现过程。
该做法的时间复杂度为
另外,本题存在
1 2 3 4 5 6 7 8 9 10 11 |
|
最长不下降子序列
最长不下降子序列问题
给定一个长度为
算法一
设
计算
容易发现该算法的时间复杂度为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
算法二2
当
回顾一下之前的状态:
但这次,我们不是要按照相同的
再看一下之前的转移:
初始时
那么,只需要找到一个
那么,根据上面的方法,我们就需要维护一个可能的转移列表,并逐个处理转移。
所以可以定义
初始化:
现在我们已知最长的不下降子序列长度为 1,那么我们让
考虑进来一个元素
- 元素大于等于
,直接将该元素插入到 序列的末尾。 - 元素小于
,找到 第一个 大于它的元素,用 替换它。
为什么:
对于步骤 1:
由于我们是从前往后扫,所以说当元素大于等于
时一定会有一个不下降子序列使得这个不下降子序列的末项后面可以再接这个元素。如果 不接这个元素,可以发现既不符合定义,又不是最优解。对于步骤 2:
同步骤 1,如果插在
的末尾,那么由于前面的元素大于要插入的元素,所以不符合 的定义,因此必须先找到 第一个 大于它的元素,再用 替换。
步骤 2 如果采用暴力查找,则时间复杂度仍然是
参考代码如下:
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 |
|
注意
对于最长 上升 子序列问题,类似地,可以令
需要注意的是,在步骤 2 中,若
在实现上(以 C++ 为例),需要将 upper_bound
函数改为 lower_bound
。
参考资料与注释
本页面最近更新:2024/8/22 12:19:26,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:ChungZH, CBW2007, dkz051, greyqz, HeRaNO, hhc0001, hsfzLZH1, Ir1d, Marcythm, ouuan, partychicken, Persdre, StudyingFather, tptpp, Xeonacid, XiaoSuan250, xyf007, zhb2000, caoji2001, Chrogeek, dong628, Enter-tainer, iamtwz, ksyx, LincolnYe, Menci, ree-chee, shawlleyw, shuzhouliu, Taoran-01, Taoran\_01, Tiphereth-A, TrisolarisHD, WAAutoMaton, xhn16729, xhn16729, yusancky, ZhangZhanhaoxiang, zychen20, zzhx2006
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用