[数据结构与算法]高楼扔鸡蛋——动态规划问题

????????今天算法课大伙做了一份课堂测验，是有关一维以及二维动态规划问题的，其中最后一天压轴的就是这道高楼扔鸡蛋问题。 在我得意洋洋以为能早早做完这份测验然后交卷的时候，我在这道题上摁是扣了半小时头皮，也没写出个所以然来，最后还是临近交卷五分钟的时候，草草写了一点自己仅有的思路。

? ? ? ? 其实我一直没读明白题目，我一直在纠结几个问题。

? ? ? ? 1. 鸡蛋的破不破跟什么有关？如果单纯的楼层到达一定高度，鸡蛋掉下来就会碎，那为什么不直接线性搜索这个楼层阈值？是否有摩擦力之类的因素导致鸡蛋在中间某些楼层掉落不会碎，而在低楼层和高楼层掉落会碎?（属于是没理解 “最差情况下” 和 “最小试验次数”）

? ? ? ? 2. 根据动态规划的SRTBOT，如果像我上面想的那样，由现有拓扑结构无法推得当前位置的值，那这个题目不是有问题了? （属于是学艺不精了）

? ? ? ? 所以下课后，当天我就找时间好好跟这道题过招了。

? ? ? ? 首先我把LeetCode上的原题目贴在这，方便大家查阅。

题目 887? ?

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足?0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足?1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

题目解析

? ? ? ? 首先，鸡蛋是在 1~i 层不会碎，在i~n层会碎。

? ? ? ? 其次，令我意外的是，单纯这个情景而不考虑是道题目的情况下，确实是可以用线性扫描的方法得到具体的楼层数。也就是从一楼开始一层一层往上，向下扔鸡蛋。反正鸡蛋没碎的话还可以用，这种方法除了累一点（也就是操作次数很多），还是很省鸡蛋的。

? ? ? ? 再者，二分查找在一定程度上也可以去求得一个解。但如果鸡蛋只剩下一个了，显然只能用线行扫描从下往上操作了。

? ? ? ? 其实回过头来看，如果不是我给自己添加了如此多的思维束缚，题目理解上也不会有很大的问题，因此我有理由相信大家在题目理解上应该没什么问题。

? ? ? ? 事实上，最重要的一条信息是，“最坏情况下”，指的就是要找的那个鸡蛋掉落恰好会碎的楼层号一定会是每次遍历的最后一个楼层，而我们要找的就是所有情况下遍历次数最少的一次。

? ? ? ? 题目读完了，该有的信息也提取了，接下来就是按照求解动态规划问题的思路去综合考虑这些元素。

? ? ? ? S: Subproblems. 这题中的子问题就是dp(k, m), k、m分别表示K和N的各种可能，也就是说有? ? ? ? ? KN个子问题

? ? ? ? R: Relation. 假设在 i 层扔下了鸡蛋，只有两种碎和没碎两种情况。碎了，就继续计算dp(k-1, i-1)；没碎，就计算dp(k, i+1). 由于题目要求最坏情况下的操作次数，所以这题子问题间的关系式为 dp(k, m) =max{dp(k-1, i-1),?dp(k, i+1)} + 1 。

? ? ? ? T:Topology. 拓扑结构由子问题和关系式来看也是显而易见了。

? ? ? ? B: Base case. 显然，要么楼层数为0，要么鸡蛋只剩一个，只能线行扫描了，算法才算结束。因此该题的 Base case 为K = 1 或 N = 0 。

? ? ? ? O: Original Problem. 原题目即为求解dp(K, N) 。

? ? ? ? T: Time. 由于dp函数中会存在一个for循环来遍历所有情况，所以算法本身的复杂度应为O(N) 。而数据的量为KN，因此求解该问题的总时间复杂度为O(KN^2) 。

? ? ? ? 自此，题目分析基本结束。

题目求解

? ? ? ? 有了上述的步骤分解，求解就显得不那么难了。

? ? ? ? 我们直接开始代码的编写吧。

??????

eggsDrop = dict() #用于记录重复的子问题的解

def dp(K, N):
    # base case
    if K == 1:
        return N
    if N == 0:
        return 0

    # 避免重复计算
    if (K, N) in eggsDrop:
        return eggsDrop[(K, N)]

    res = float('INF')

    # 穷举所有可能的选择
    for i in range(1, N + 1):
        res = min(res,
                  max(
                      dp(K, N - i),
                      dp(K - 1, i - 1)
                  ) + 1
                  )

    # 记入字典
    eggsDrop[(K, N)] = res

    return res

? ? ? ? 其实代码十分明了。这里我们用了一个字典来记录出现过的子问题的解，这样能大大降低程序运行的时间复杂度。

? ? ? ? 程序的主要部分也就只有一个 for 循环，i 表示楼层号，因此这个循环就是用于穷举鸡蛋在不同楼层作为第一次抛下的所有情况。

????????

? ? ? ? 这篇文章仅作为一份小小的心得笔记，记录对此问题的思考与体会。