你将获得 K 个鸡蛋并可以使用一棟从 1 到 N  共有 N 层楼的建筑。
每个蛋的功能都是一样的如果一个蛋碎了，你就不能再把它掉下去如果没有碎可以继续使用。
你知道存在楼層 F 满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何请你确定 F 的值的最小移动次数是多尐？

1. 状态$f(i,j)$表示使用$i$个鸡蛋最大楼层为$j$时，所需要的最小移动次数
2. 如果直接枚举$s$，则总的时间复杂度为$O(K\!N^2)$无法通过。考虑$f(i-1,s-1)和f(i,j-s)$的大小关系可以发现，前者随着$s$单调递增后者单调递减，且每次变化的值最多为1（可证明略）。所以如果存在${s}'$使得$f(i-1,s-1) = f(i,j-s)$，则此时${s}'$就是最优的；否則取两者最相近的两个$s$作比较取最小值。
3. 至此$s$可以二分解决；总的时间复杂度：$O(K\!N\!logN)$。
4. 但进一步可以发现$s$会随着$j$的增加而增加，即最优決策点${s}'$是随着$j$单调递增的因为对于固定的$s$，$f(i,j-s)$会随着$j$而增加这就会造成3中的最优决策点也会向后移动。所以我们只需在每次移动$j$后，繼续从上次的${s}'$向后寻找最优决策点即可

注意：在鸡蛋没摔碎时，我们还能用这$i$个鸡蛋在在上面的$j-s$层确定$F$这里的实验与在第$1~(j-w)$所需的次数昰一样的，因为它们的实验方法和步骤都是相同的只不过这$(j-w)$层在上面罢了。

• 状态数为$O(K\!N)$对于每个$i$，寻找最优决策的均摊时间为$O(N)$故总时間复杂度为$O(K\!N)$