24.高层扔鸡蛋问题：有一个100层的高楼，给你两个鸡蛋，需要测试出在哪层楼扔鸡蛋，鸡蛋不会碎。鸡蛋如果没有碎可以扔无数次。最少需要扔多少次？

这是一个非常经典的动态规划问题，手撕代码时也很常见

如果是只有1个鸡蛋，这个问题就很简单了，为保证一定找到这个楼层，只能从第一层开始试。

题目中是两个鸡蛋，正常就是会想到二分法之类，先在50层扔一个，没碎，捡回来在75层扔，碎了，第二个鸡蛋只能从第1层开始试了。第一个鸡蛋用来缩短范围，第二个鸡蛋用来遍历范围。

假设需要x次才能找到临界的楼层，也就是说第一个鸡蛋从第x层扔出（因为需要考虑最差情况，万一第一个鸡蛋碎了，为保证x次能找到，第一个鸡蛋需要从x层扔出。因为如果鸡蛋恰好在第x层碎了，在第x-1层没碎，第一个鸡蛋在x层以上的楼层扔的话，第二个鸡蛋需要遍历x次，一共需要x+1次）

如果第一个鸡蛋碎了，第二个鸡蛋遍历1至x-1层，则需要x次找到。

如果第一个鸡蛋没碎，则第一个鸡蛋的任务是需要继续缩小范围，还是为了保持这个x次能找到临界楼层的条件，现在只剩x-1次了，下一次只能在x+x-1层扔第一个鸡蛋，以此类推，x+(x-1)+(x-2)+……+1>=100，x=14

也就是说最少需要扔14次。

这个问题还有一些变种问题，比如2个鸡蛋，n层楼；k个鸡蛋，n层楼（力扣887题，大家感兴趣可以看看）

本站链接：https://www.mianshi.online，如需勘误，请联系微信：lurenzhang888

---

点击面试手册，获取本站面试手册PDF完整版