动态最优化经典面试题

最近看到了一条史前的算法面试题，觉得挺有意思的，虽然网上已经有了很多完善的答案，但是我还是想自己整理一遍，强化印象，同时也和大家分享一下这道12年的Google题目：

一幢 200 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎？

先形象的理解一下这道题目，假设第一个蛋我们放在了i层，有两种case，碎或者不碎。 先看简单的结果， case1:如果碎了，为了求出层数，那么我接下来的那颗蛋需要从第1层开始尝试i-1次，因为我们不允许冒第二次碎的风险了，这很好理解。 case2:如果没碎，我们得知一条新的信息，那就是我们要求的目标层在i层之上，但是我们依旧不知道是哪一层，假设是m层（m>i）,那么同样的，和第i层一样，面临2个case，碎或者不碎。

这时候，我们的前提是在最恶劣的情况下，保证我们的每次的风险都尽可能的小，至少要少于上一次的风险。

我们可以让新的m的高度为i+i-1,其中，i是第一次我们放的层数，i-1是我们选择的风险若于第一次风险的层数高度，类推下去：i+i-1+i-2+i-3+...+1=200，得到i=20，就是我们第一次应该放的位置，同理第二次如果没有碎应该放的就是39...

我个人对这道题目的理解中，其实就为了平分风险，让每次碎的高度都相等，也就是i-1 = m-i-1+1==>m=2i-1

这边的python代码网上也有很多，这边我罗列一个我写的，可能和别人的不一样，实现效率也可能较慢，建议大家在网上搜完善版本的，仅供大家熟悉上述的描述：

#n为层数，m为蛋数，f函数为求最优层数
def f(n, m):
#如果是0层的，返回最优层数为0
    if n == 0:
        return 0
#如果只有一个鸡蛋，必须要从最低层开始试，所以为当前最安全层n
    if m == 1:
        return n
#这边我们来看，f(i - 1, m - 1)是如果i层碎了，我们需要计算i-1层下的情况，同时减少一颗蛋；
#f(n - i, m)是i层没碎，那相当于安全层从0变成了n，要计算的就是相当于有 f(n, m)变成了 f(n - i, m)
#最后在最大化风险下找出其中风险最小的层数即可
    best_floor = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)] + 1)
    return best_floor

结果：

In [74]:print(f(100, 2))    
14

这边f(200,2)实在没跑出来，时间太久了，所以跑了100，2的结果，迭代次数超多，具体我没有算过，建议优化一下计算的代码再执行。

最后谢谢大家阅读。