DP 优化微剖

引言

学习朱晨光《从《鹰蛋》一题浅析对动态规划算法的优化》的笔记

鹰蛋问题引入

有一堆共 M 个鹰蛋,一位教授想研究这些鹰蛋的坚硬度 E。

他是通过不断 从一幢 N 层的楼上向下扔鹰蛋来确定 E 的。当鹰蛋从第 E 层楼及以下楼层落下时是不会碎的,但从第(E+1)层楼及以上楼层向下落时会摔碎。

如果鹰蛋未摔 碎,还可以继续使用;但如果鹰蛋全碎了却仍未确定 E,这显然是一个失败的实验。教授希望实验是成功的。

例如:若鹰蛋从第 1 层楼落下即摔碎,E=0;若鹰蛋从第 N 层楼落下仍未碎, E=N。这里假设所有的鹰蛋都具有相同的坚硬度。

给定鹰蛋个数 M 与楼层数 N。 要求最坏情况下确定 E 所需要的最少次数。

样例输入

M=1,N=10

样例输出

ANS=10

样例解释

为了不使实验失败,只能将这个鹰蛋按照从一楼到十楼的顺序依次扔下。一旦在第(E+1)层楼摔碎,E 便确定了(假设在第(N+1)层摔鹰蛋会碎)。那么最坏情况就是在第 N 层仍未碎,则次数为 10,E=10.

初步 DP

乍一看题目比较玄学,我们就从玄学的 DP 开始想。题目中有两个维度:鹰蛋个数和楼的高度,那么我们想办法利用这两个维度。

定义 表示用 个蛋,在高度为 的楼实验的最坏情况下的最少次数。

考虑第 个蛋分别在第 层的实验情况,在第 层实验:

  1. 摔碎,说明 ,但仍没有确定 ,因此还需要用剩下的 个蛋在 层继续实验;
  2. 未碎,说明 ,仍没有确定 ,还需要用 个蛋在 层,即层数为 的楼,继续实验。

题目中所说的最坏情况,即要求上述两种情况取最大值。

最坏情况的最小次数,即对于所有 的最坏情况取最小值。

转移方程如下:

复杂度分析

显然鹰蛋的个数不超过楼层的高度,那么令 ,则复杂度为 ,空间复杂度用滚存优化为 .

二分剪枝

其实大多数人看到这道题的第一个反应怕不是 DP 而是二分。正常思维来看,应该是在高度为 N 的楼上二分着丢蛋对吧。这时的最坏情况次数为 ,并且是可以达到的下限。

因此,一旦 ,就可以直接输出 ;否则再进行上述 DP 过程。

时间复杂度降为 ,空间复杂度仍为 .

单调性分析

引理 1

证明

那么 (一个蛋要最坏扔 次),显然 成立。

即当 j=1 时,不等式成立

假设不等式对 都成立,那么

根据假设有

二分查找最优决策

有了上述单调性引理,那么观察一下 DP 方程:

  • 是关于 非严格单调递增的;
  • 是关于 非严格单调递减的。

那么取他们的最大值的最小值显然就是当两个值最接近的时候啦

所以状态转移的时候二分一下就可以啦

复杂度分析

状态转移复杂度从 降到 ,整体时间复杂度为 ,空间复杂度仍然为滚存, .

挖掘转移方程

引理 2

证明

推论

根据引理 1,有 .

的状态空间是离散,线性,非严格单调,连续的。

转移策略

根据上述推论,可以想到以下的转移策略:

  • 如果存在 使得 ,那么就让 .
  • 否则,即不存在上述 ,那么令 .

因此我们维护一个指针 满足:

  • .
  • .

那么显然有以下推论:

  • .
  • .

挖掘方程

对于 DP 方程

对于上述方程中状态空间 ,显然我们可以找到一个对应的指针 .

显然 .

Case1

.

那么 .

根据转移策略可知,此时 .

Case2

.

此时我们考虑 的各个决策的可行性

那么根据引理 1

因此 的决策无法使得 .

只是把 变成了 ,而 的部分没有改变,同样无法使得 .

根据 指针的定义以及定义域

显然无法使得 .

综上所述,在 的情况下无法使得 .

因此根据转移策略, .

算法设计与复杂度分析

综上所述,我们只需要对每一个 找到对应的指针 ,然后考虑决策 的大小情况,即可实现 的转移。

那么如何找到决策 呢?显然我们只需要在遍历第二维的时候顺便 维护一下即可

转移的复杂度从 降为 ,整体时间复杂度 ,空间上仍采用滚动数组,复杂度为 .

优化小结

回顾一下所讲到的四个部分:

  1. 首先根据问题列出状态并设计了 DP 方程
  2. 根据问题上界的分析简化算法,减小了算法上界复杂度
  3. 分析转移方程蕴含的单调性,采用二分转移的方式,减少转移复杂度
  4. 深入方程的数学本质,挖掘状态转移的有界性和可行性,只选择有效且可行的状态转移子空间,减少转移复杂度

全新的角度

上述动态规划的算法复杂度在数次优化后为 ,现在我们从另一个角度审视问题

考虑 表示用 个蛋尝试 次在最坏情况下能确定 E 的最高楼层数

  • .(无论有多少个鹰蛋,只试一次,还要求确定 E,就只能确定第一层楼)
  • .(只有一个鹰蛋,试 次,要确定 E,最坏就是把 层楼试完,则楼层数为

状态转移则较为简单。因为要最大化楼层数,就无法确定丢蛋的具体位置,那么分两种情况

  • 如果在某一层丢下去碎了,就要用余下的 个蛋试 次确定楼层的高度。既然我们希望楼层越高越好,这就是一个子问题,即为 .
  • 如果没摔碎,就用余下的 个蛋试 次在上面的楼层确定高度。仍然是一个子问题,即为 .

因此转移方程为 .

目标: .

复杂度初步分析

用上二分剪枝,时间复杂度 ,空间上使用滚存,复杂度为 .

但其实这并不是严格的复杂度,下面给出严格复杂度上限的推导

与组合数

容易发现, 与组合数函数 极其相似:

易证, .

放缩法

的时候,有 .

时,根据 的定义有

接下来考虑一下 的上界。

引理 3

时, .

由函数图像即可知。

p1

根据引理 3,有 .

即, .

综上所述, .

这说明 的实际计算量是 级别的。不过这也是一个大概的上界

感性图像解读

貌似论文的后面不那么严谨了,直接上图。

画出 的图像:

其中蓝色为 ,红色为 ,绿色为 .

p3

于是我们可以大致感性证明, 同阶

那么也就是说, 是与 同阶的,因此实际时间复杂度为 .

总结

文章讲述了两种思考角度不同的 DP,对其中一种主以优化讲解,另一种主以复杂度分析讲解,十分有意思

参考文献

[1] 朱晨光。从《鹰蛋》一题浅析对动态规划算法的优化。IOI2004 国家集训队论文


  转载请注明: Sshwy's Blog DP 优化微剖

 上一篇
可持久化数据结构(二) 可持久化数据结构(二)
引言本文上接《可持久化数据结构(一)》,简单介绍了动态主席树。然后主要讲解了各类求第 K 小值的算法。 权值线段树的运算仍然是主席树的部分,我们先系统讲解权值线段树的运算 考虑两颗结构相同的权值线段树 ,那么定义有如下运算:
2019.01.23
下一篇 
可持久化数据结构(一) 可持久化数据结构(一)
前言有没有发现,很多数据结构的前面加上一个 “可持久化”,难度就上了一两个档次? 本文就从基础的可持久化数组入门,同时解释可持久化的含义 例题引入LuoguP3919【模板】可持久化数组 如题,你需要维护这样的一个长度为 N 的数组,支
2019.01.19
  目录