LeetCode887之鸡蛋掉落（相关话题：动态规划,二分法）

前言

但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承咱们号一贯的作风，拒绝奇技淫巧，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了不太划算

问题描述

一幢 n层的大楼,给你k个鸡蛋. 如果在第 i层扔下鸡蛋,鸡蛋不碎,那么从前 i-1 层扔鸡蛋都不碎.这k(k>1)只鸡蛋一模一样,不碎的话可以扔无数次. 已知鸡蛋在0层扔不会碎.提出一个策略, 要保证能测出鸡蛋恰好不会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

问题分析

1）最坏情况下所扔次数最少，比较绕口。想表达的意思是，在不明确知道哪一层会碎的情况下，要找到一种策略，通过最少的试验次数，得到临界楼层（恰好不会碎的楼层）。不明确知道，就需要考虑最糟糕的情况，而且这种策略与其他策略相比是最糟糕的情况下，最少的试验次数。

2）假设一种扔法：第一个鸡蛋，从50楼扔下去。如果碎了，第二个鸡蛋必须从1~49层逐层试验。如果第i层为临界层，且i≤49，这个时候，要试验的总次数是1 +（i - 1）。因为必须保证在没找到临界楼层之前，鸡蛋不能碎。如果没碎，则第一个鸡蛋可以接着从75层扔。因为即使这次碎了，还有k-1个鸡蛋，可以继续试验。对第一个鸡蛋的继续从中间分，就比较合理。

3）假设到代数：如果第一枚鸡蛋扔下去的层数为i，则碎了的情况，需要扔的总次数最糟糕的情况是1 + ( i - 1 )；如果没碎，剩下的k-1个鸡蛋都在，需要扔的次数一定为1 + 用k枚鸡蛋来解决剩下的n- i层的次数&#