扔瓶子测楼层
一栋楼有n层，需要测试某种材质的玻璃瓶从哪一层掉下来恰好会碎。现在仅有两个这样的瓶子。请问怎样仍才能最快的测出楼层的临界值？
A. 只用一个瓶子从第一层扔到第n层
找到临界值的扔瓶子次数的期望为每一层的期望次数之和
1 | E(x) = 1/n * 1 + 1/n * 2 + 1/n * 3 + ... + 1/n * n = (1+n)/2 |
所以时间复杂度是O(n)
B. 用贪心的思维
第一个瓶子从第1层开始扔，每次层数翻倍，依次为，1，2，4，8，16，直至在第 2^k 层碎掉。
第二个瓶子从第 2^(k-1) 层开始扔，直至第 2^k 层为止，中间肯定能找到临界值。
所以时间复杂度是O(lgn)
C. 用二分法
第一个瓶子每次以(i, j)为区间，扔的位置为(i+j)/2, 初始情况, i=0,j=n, 如果瓶子没碎，则i=j，直至碎掉。
第二个瓶子从第 i 层开始扔，直至第 j 层为止，中间肯定能找到临界值。
对于第 i 层，扔的情况为：
- 第一个瓶子：n/2, $/2+n/4 i, n/2+n/4+n/8
- 第二个瓶子：n/2+n/4, (n/2+n/k+1), …, i
显而易见，时间复杂度是O(n)
D. 数学推算
这个题目是需要最快的找出临界值，可以转换为，即使在最坏的情况下，也能最快地找出临界值。
我们先假设最坏情况下，瓶子下落次数为x，即我们为了找出N，一共用瓶子做了x次的实验。
那么，我们第一次应该在哪层楼往下扔瓶子呢？
先让我们假设第一次是在第y层楼扔的瓶子，如果第一个瓶子在第一次扔就碎了，我们就只剩下一个瓶子，要用它准确地找出N，只能从第一层向上，一层一层的往上测试，直到它摔坏为止，答案就出来了。
由于第一个瓶子在第y层就摔破了，所以最坏的情况是第二个瓶子要把第1到第y-1层的楼都测试一遍，最后得出结果，噢，原来瓶子在第y-1层才能摔破(或是在第y-1层仍没摔破，答案就是第y层。) 这样一来测试次数是1+(y-1)=x，即第一次测试要在第x层。
OK，那如果第一次测试鸡蛋没摔破呢，那N肯定要比x大，要继续往上找，需要在哪一层扔呢？我们可以模仿前面的操作，如果第一个瓶子在第二次测试中摔破了，那么第二个瓶子的测试次数就只剩下x-2次了(第一个瓶子已经用了2次)。这样一来，第二次扔瓶子的楼层和第一次扔瓶子的楼层之间就隔着x-2层。
我们再回过头来看一看，第一次扔瓶子的楼层在第x层，第1层到第x层间共x层；第1次扔鸡蛋的楼层到第2次扔瓶子的楼层间共有x-1层(包含第2次扔瓶子的那一层)，同理继续往下，我们可以得出，第2次扔瓶子的楼层到第3次扔瓶子的楼层间共有x-2层，最后把这些互不包含的区间数加起来，应该大于等于总共的楼层数量100，即
1 | x + (x-1) + (x-2) + ... + 1 >= 100 |
即我先用第1个瓶子在以下序列表示的楼层数不断地向上测试，直到它摔破。 再用第2个瓶子从上一个没摔破的序列数的下一层开始，向上测试，即可保证在最坏情况下也只需要测试14次，就能用2个瓶子找出从哪一层开始，往下扔鸡蛋，瓶子就会摔破。
1 | 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 |
E. DP的解法
假设f(n)表示从第n层楼扔下鸡蛋，没有摔碎的最少尝试次数。第一个鸡蛋，可能的落下位置[1,n],第一个鸡蛋从第i层扔下，有两种情况：
- 碎了，第二个鸡蛋，需要从第一层开始试验，有i-1次机会
- 没碎，两个鸡蛋，还有n-i层。这个就是子问题了f(n-i)
所以，当第一个鸡蛋，由第i个位置落下的时候，要尝试的次数为 1 + max{i - 1, f(n - i)}，那么对于每一个i，尝试次数最少的，就是f(n)的值。
状态转移方程如下：
1 | f(n) = min{1 + max{i - 1, f(n - 1)}} |
其中: i的范围为[1, n], f(1) = 1.
F. 推广到一般化的问题
为n层楼，m个鸡蛋。
如下分析： 假设f(n,m)表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下，有两种情况：
- 碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全楼层，还需要f(i-1,m-1)次，找到子问题
- 不碎，上面还有n-i层，还需要f(n-i,m)次，又一个子问题。
状态转移方程如下：
1 | f(n, m) = min{1 + max{f(n - 1, m - 1), f(n - i, m)}} |
其中： i为[1, n], f(i, 1) = 1
Reference
http://www.cricode.com/3558.html
https://gist.github.com/sing1ee/5971946
