主题：【原创】由一个简单的面试题想起的 -- 东方射日

问的到底是什么,是很关键的。到底是要期望次数最小，还是要最坏情况下(worst case)次数最小？如果是前者，不给出概率分布是没法做的。楼下很多假设平均概率，虽然很合理，但属于自己擅自加的条件了。考虑到东方射日很可能是面试的计算机职位，又考虑到很多类似的问题也是要求最坏情况下最优解（比如１２个砝码其中一个与其它不同，要求用一个天平把它找出来），我觉得后者的可能比较大。

如果确实是要找最坏情况下最优解，那么用动态规划是很简单的。

假设f(x)代表x次试验最坏情况下最多能覆盖的楼层数。那么

f(0)=1

f(n)=n+f(n-1)

递归式的解释是这样的。在允许n次试验时，第一次试验在n+1楼层。分情况讨论。假如摔坏，那么1<=M<=n,剩下的一个好包裹能保证在最坏情况下用n-1次试验找到M。假如不坏，那么n+1<=M<=N,两个包裹还都是好的，根据递归假设，用n-1次试验还能覆盖f(n-1)个楼层，所以N-(n+1)+1=f(n-1), N=n+f(n-1)。

所以f(n)=n(n+1)/2+1。

验算一下。f(3)=3(3+1)/2+1=7。方法是，第一次试４。假如破，剩下一个从２往上试（因为根据前提条件，1<=M<=N,所以第一层一定是安全的，从楼下东方射日回复三力思看，我怀疑这个前提条件是不是给错了？不过这个没多大关系，0<=M<=N答案也差不多。）最坏情况下一直到3都不破，又试验了２次，共３次。假如在４不破，4<=M<=7,第二次试验6。假如在６破了，第三次试验５；假如在６不破，第三次试验７。