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

m个蛋，最坏情况下扔n次，所能涵盖的楼层为f(m,n)

1. 当m=1, f(m,n)=n

2. 当m>n, f(m,n)=f(n,n)

3. 当n>=m>1,f(m,n)=f(m-1,n-1)+f(m,n-1)+1

于是,显然地,m个蛋，s层楼，最坏情况下需要扔

min{n;f(m,n)>=s}次。

举个例子，2个蛋，f(2,n)=f(1,n-1)+f(2,n-1)+1=n+f(2,n-1)=n+...+1

4个蛋，

f(4,1)=f(1,1)=1

f(4,2)=f(2,2)=f(1,1)+f(2,1)+1=f(1,1)+f(1,1)+1=3

f(4,3)=f(3,3)=f(2,2)+f(3,2)+1=f(2,2)*2+1=7

f(4,4)=f(3,3)+f(4,3)+1=15

f(4,5)=f(3,4)+f(4,4)+1=f(2,3)+f(3,3)+16=6+7+16=29

f(4,6)=f(3,5)+f(4,5)+1=f(2,4)+f(3,4)+f(3,4)+f(4,4)+3=10+13+13+15+3=54

就是说，4个蛋，20层楼，最坏需要扔5次。50层楼，需要6次。