algorithm - 广义的两蛋拼图

Question

问题描述如下:

假设我们想知道 N 层建筑物中的哪些楼层可以安全地掉落鸡蛋，以及哪些楼层会导致鸡蛋在着陆时破裂。我们做一些假设:从跌落中幸存下来的鸡蛋可以再次使用。

• 必须丢弃破损的鸡蛋。
• 跌倒对所有鸡蛋的影响都是一样的。
• 如果鸡蛋掉在地上会碎，那么如果从更高的窗口掉下去，它也会碎。
• 如果一个鸡蛋从跌落中幸存下来，那么它在较短的跌落中也能存活下来。
• 不排除一楼 window 打碎鸡蛋，也不排除N楼 window 不打碎鸡蛋。

给定一个 N 层楼的建筑和 d 个鸡蛋的供应，找到最小化(在最坏情况下)确定断层所需的实验跌落次数的策略。

---

我已经看到并解决了 2 个鸡蛋的问题，其中 N=100 的答案是 14。我试图使用 DP 了解 wiki 的通用解决方案，但无法理解他们试图做什么。请告诉他们他们是如何到达 DP 的以及它是如何工作的？

编辑:

this 中给出的重复d滴和e蛋可以测试的最高层的文章如下:

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

递归很好，但我无法理解它是如何推导出来的？

这个解释对我来说不是很清楚....我只是希望有人用更清楚的话向我解释这种复发。

Answer 1

(1) 考虑第一滴打破鸡蛋的情况。 然后当且仅当它至多为 f[d-1, e-1] 时，您才能确定破地板。因此，您不能从高于 f[d-1, e-1] + 1 的位置开始(当然也不应该从更低的位置开始)。

(2) 如果你的第一次掉落没有打碎鸡蛋，你就是 f[d-1, e] 的情况，只是从你第一次掉落的地板 + 1 开始, 而不是 1 楼。

所以，你能做的最好的事情就是在 f[d-1, e-1] + 1 层开始丢鸡蛋(因为 (1))，你最多可以f[d-1, e] 层比那个高(因为(2))。那是

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]