题意分析

这道题目的意思有许多需要明确的地方：

1. 题目中写道“确定 F 的值的最小移动次数是多少”，这边的最小移动次数是基于最坏情况下，否则运气好的情况下最小移动次数就是1次了。在手上有多余的鸡蛋情况下，可以“碰运气”（选择最佳尝试方案）；但是如果手上只有一个鸡蛋，就不能碰运气了，不能“冒险”从高层尝试，如果碎了就不能进行后续的实验了，所以必须从最低层的楼层开始尝试，依次往上尝试，如果在x层碎了，那么F=x-1，由于是最坏情况，所以F=n。

2. 没有碎的鸡蛋可以继续用于后续实验的尝试，这也符合实际情况。

用K=1,N=3举例说明什么是最坏情况：手里只有一个鸡蛋，不能从2楼尝试，如果碎了并不能说明1楼就一定不碎，还要尝试从1楼扔下，但这时候已经没有鸡蛋可用了，所以方案不成立。

所以题意转化为：如果手里只有一个鸡蛋，必须从最低层依次往上尝试；手里有多个鸡蛋则要确定最佳尝试方案，得到最小尝试次数；没碎的鸡蛋可以再次使用。

区间转化

一种朴素的想法是可以二分楼层进行尝试，首先说明这种方法是错的！！，但是可以帮助我们改进算法。

设x是中间一层楼，在尝试x楼之后，依据鸡蛋的情况我们需要继续尝试[1,x-1]楼或[x+1,n]楼，由于要考虑最坏情况，所以上面的楼层和下面的楼层都要考虑，并取两者中尝试次数多的情况作为结果。

有区间列出来了，自然想到往动态规划上靠，尝试把手里的鸡蛋数也加进去,k为手里的鸡蛋数，dp为最小尝试次数：

其中+1是代表x层尝试了一次，左边dp中的k-1代表鸡蛋已经碎了，手头可用的鸡蛋数减1；右边dp中的k代表鸡蛋没碎，继续使用。取两次最小尝试次数的最坏情况。

然而题目中的n的最大值为10000，k的最大值为10，[10][10000][10000]的数组显然超出内存限制。

可以把[1,x-1]楼和[x+1,n]楼这个区间转化成楼层数。举个例子，[1,3]楼和[4,6]的处理过程是一样的，因为它们的楼层数量相同（都是3层），只是基准不一样。把区间转化成楼层数后：

注意这时候n代表了楼层数量，左边dp是鸡蛋碎了的情况下还要处理下面的x-1层，右边dp是鸡蛋没碎的情况还要处理上面的n-x层。这时[10][10000]的空间显然满足，并且重叠子问题更多。

x楼层的选择

之前把x楼层设置为中间这层楼，但是这种方法是错的：第一，中间楼层的定义就不能明确，中间是指(n+1)/2还是n/2，又或者是(n-1)/2；第二，只选择中间楼层的策略是错误的，可以从提交不通过的样例中得知。

既然最佳选择的x楼层位置不能给出，那么就将动态规划进行到底，遍历各个可能的x楼层：

在之前的式子外面添加了min，即遍历x楼层的所有可能，取结果最小的（因为要最小移动次数）。

本来到这问题应该算是结束了，但是O(K*N*N)的时间复杂度会超时。

二分搜索

如果固定k，那么dp[k,n]是关于n的递增函数，这点容易理解：楼层数越多，需要尝试的次数就会越多；最后只剩一个鸡蛋时，依次尝试的次数也会越多。由dp[k,n]固定k的单调性，可以画出固定k时，1+dp[k-1,x-1]和1+dp[k,n-x]关于x的图像：

1+dp[k-1,x-1]关于x递增，1+dp[k,n-x]关于x递减，max{1+dp[k-1,x-1],1+dp[k,n-x]}就是图中的粗线部分，而min{max{1+dp[k-1,x-1],1+dp[k,n-x]}}就是求粗线部分组成图像的最小值。可以用二分搜索求得最佳x，这时算法的时间复杂度变为O(K*N*lgN)。

可以算出1+dp[k-1,mid-1]和1+dp[k,n-mid]，根据它们的大小判断是更新left，还是更新right：如果1+dp[k,mid-1]≤1+dp[k,n-mid]则更新left的值，反之更新right的值。由于最终的值为整数，最终的结果一定是left在最小值的左边（或者重合）并且right在最小值的右边，最后分别计算一下两者谁最小就是图像的最小值。

代码实现