dropegg 

1
有座N层的建筑，请你用两个相同鸡蛋确定鸡蛋可以安全落下的最高位置，求最少的尝试次数。

  1. 逐层尝试
    首先想到的是最简单的办法是一层开始往上试。那么显然最坏情况是在最后一层不能安全降落，此时尝试次数为N-1。时间复杂度为O(N)

  2. 二分尝试
    我们还容易想到2分的办法。第一次在N/2层，如果碎了回到一的办法一层层向上检查{1,N/2-1}层，如果没碎则继续2分考察3/4*N层。
    此方法最坏情况发生在第一次鸡蛋就碎了，此时我们需要从第一层，或者N/2层开始，依次向上试。需要尝试N/2次，时间复杂度为O(N)

  3. 动态规划
    上述两种方案都不够好，对于方法1尝试的太过保守，导致大量丢第一颗蛋。方法2尝试的太过激进，需要大量丢第二颗蛋。可以发现，如果第一颗鸡蛋碎了后，第二颗鸡蛋的尝试次是恒定的，它将只能从上一次没碎的未知到这次碎了的未知逐一检测。发现这个性质后，我们考虑使用动态动态规划。
    设F(i)表示i层楼梯两个鸡蛋最少需要尝试的次数。
    对于i层高的建筑，假设第一颗鸡蛋在第K层丢下。它如果碎了，则第二颗鸡蛋需要向下需要尝试K-2次。而如果没碎，则仍然使用第一颗鸡蛋，测试剩下的i-k层。

    F(i) = 1+min{K-2, F(i-k)} k = 1 to i
    时间复杂度为O(n^2)

  4. 二项式
    有没有更好的办法呢？我们考虑对于每一个检测区间的最大尝试次数是恒定的都为最少尝试册数。设对于n层高的建筑，最少尝试次数为x。
    第一个鸡蛋最高在第x层丢下，如果碎了则满足最少尝试为x的假设。如果没碎，由于已经尝试过一次，第二次鸡蛋需要在x+x-1层扔下
    …
    考虑第i次，尝试的位置应为x+(x-(i+1))
    则最少尝试次数为x，最多可以测试(1+2+..+x)层楼
    那么对于n层楼，找到最小的x使得(x+1)*x/2 >= n 即可。

    利用二项式定理，时间复杂度为O(1)

#问题的扩展
问当有m个鸡蛋，测试n层建筑，最少的尝试次数。

  1. 考虑扩展之前的动态规划方法，使其成为二维：

    1
    f(i, j)表示i层楼梯j个鸡蛋最少需要尝试次数
考虑第i颗鸡蛋在第k层楼落下：
    如果碎了，则失去了一个鸡蛋，需向下检查k-1层楼，即子问题f(k-1, j-1)。
    如果其没碎，则鸡蛋不变，需向上检查的i-k层楼，即子问题f(i-k, j)。
f(i,j) = {
min{1 + max(1+max(f(k-1, j-1), f(i-k, j)}, where j > 1 and k = j-1 to i-j
i, where j == 1
复杂度为O(n^3)

  2. 问题的转换
    上面办法复杂度太高，考虑给定球数i和尝试次数j最多能测多少层楼f(i, j)。
    寻找第i次丢球的位置的最佳位置k，可以证明其最佳的丢球位置必然为f(i-1, j-1)+1。

证明：

1
如果k大于f(i-1,j-1)+1，k如果碎了，根据定义最多可以测试f(i-1,j-1)层楼 < k-1，方案不可行。
如果k低于f(i-1,j-1)，k如果没碎，它往上最多能测f(i,j-1)层楼不变。而k < f(i-1, j-1)，显然逊于f(i-1,j-1)
得证！

从而可以得到f(i,j)的递推式：

f(i, j) = f(i-1, j-1)+f(i, j-1)+1
找到第一个j使得f(m, j) >= n 即可
此时复杂度为O(n^2)