高楼扔鸡蛋问题是典型的动态规划问题

文章目录

• • 1. 高楼扔鸡蛋
  • 2. 猜数字大小

1. 高楼扔鸡蛋

给你k个完全相同的小球，并且在一个有n层楼（从第1层到第n层）的大楼上。
特定存在的楼层f（其中0 <= f <= n），满足任何从高于该楼层（即大于等于该楼层）落下的小球都会破碎；而从该楼层或以下落下的小球则不会破碎。
每一次操作中，请你拿出尚未破损的一个小球，并将其从任意一层x抛出（这里x必须满足1 <= x <= n）。如果该次操作后小球破碎，则不能再继续使用它；但如果此次抛掷未导致破碎，则可以在后续的操作中重复使用这个小球。
请计算确定特定存在的楼层f所需的最少操作次数。

实例
输入参数设定为 k=1 和 n=2。
测试结果表明需要执行两次尝试。
解释：
将鸡蛋从第1层开始下落测试。
若第一次尝试失败，则确定最大抗摔次数f为0次。
若第一次尝试成功，则进入第二阶段测试。
将鸡蛋从第2层开始继续测试。
若第二次尝试失败，则确定最大抗摔次数f为1次。
若第二次也成功，则确定最大抗摔次数f为2次。
由此可见，在最糟糕的情况下最多需要两次尝试即可确定最大抗摔次数f的值。

若仅采用二分法进行操作，则在某些特定情况下会遇到无法找到准确答案的挑战。例如仅有一个鸡蛋可用时，在8层高的建筑中简单地将范围分为两半后仍无法确定具体位置，则必须逐一排查才能找到正确的楼层。因