这是问题描述:
假设我们希望知道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
复发很好,但我不明白它是如何产生的?
对我来说,解释不清楚。…我只希望有人用更清晰的语言向我解释这种复发。
(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]