一尘不染

广义二蛋拼图

algorithm

这是问题描述:

假设我们希望知道N层建筑物中的哪个故事可以安全地放下鸡蛋,并且哪些会导致鸡蛋在着陆时破裂。我们做出一些假设:可以再次使用从秋天跌落下来的鸡蛋。

  • 破蛋必须丢弃。
  • 跌倒的影响对于所有鸡蛋都是相同的。
  • 如果鸡蛋掉落时破裂,那么如果从较高的窗口掉落,鸡蛋也会破裂。
  • 如果鸡蛋在跌落中幸存下来,那么它将在较短的跌落中幸存下来。
  • 不排除第一层的窗户破鸡蛋,也不排除第二层的窗户不破鸡蛋。

给定一个N层故事楼并提供d个鸡蛋,则找到一种策略(在最坏的情况下)将确定跌落地板所需的实验降落次数减至最少。


我已经看到并解决了2个鸡蛋的问题,对于N =
100,答案为14。我试图使用DP从Wiki理解通用解决方案,但无法理解他们正在尝试做什么。请告诉他们他们如何到达DP以及它是如何工作的?

编辑:

本文中针对可以用d滴和e卵测试的最高楼层的递归如下:

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

复发很好,但我不明白它是如何产生的?

对我来说,解释不清楚。…我只希望有人用更清晰的语言向我解释这种复发。


阅读 213

收藏
2020-07-28

共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]
2020-07-28