笔试题：扔鸡蛋

100层的楼，两个相同的鸡蛋，设计一个扔鸡蛋的策略，来得到鸡蛋破裂的临界层，并使得最坏情况下扔鸡蛋的次数最少。

动态规划
设 f(n,k) 为n层楼，k个鸡蛋时，最坏情况下扔鸡蛋的次数
假设第一次在 r 层扔第一个鸡蛋， 1<=r<=n 则

f(n,k)= min{max(f(r-1,k-1),f(n-r,k))+1},1<=r<=n  for k>=2,n>=1

f(n,1)=n

f(0,k)=0

亦即，choices 为第一次在 r 层扔第一个鸡蛋
如果鸡蛋破裂，则还需要 f(r-1,k-1) 次
如果鸡蛋不破裂，则还需要 f(n-r,k) 次
因为求最坏情况下，所以取二者的最大值
choice 的选择为求最小值
如上算法的解为 14 次

如果记录 choice 的话，第一次在第9层扔
这只是最优解之一
比如另一最优解为
首次在14，然后在27，39...

类似的笔试题还有
300层的楼，3个鸡蛋
答案为13次

代码

unsigned maxNum(unsigned storey, unsigned egg)
{
 if(storey==0)
  return 0;
 if(egg==1)
  return storey;

 vector<vector<unsigned>> table(storey+1,vector<unsigned>(egg+1,0));

 for(unsigned k=1;k<=egg;k++)
  table[0][k]=0;

 for(unsigned n=1;n<=storey;n++)
  table[n][1]=n;

 for(unsigned k=2;k<=egg;k++)
  for(unsigned n=1;n<=storey;n++)
  {
   unsigned tmin = storey;
   unsigned ostorey=1;
   for(unsigned r=1;r<=n;r++)
   {
    unsigned tmax = max(table[r-1][k-1],table[n-r][k])+1;
    tmin = tmax<tmin?tmax:tmin;
   }
   table[n][k]=tmin;
  }
 return table[storey][egg];
}