Shellbye.github.io
Shellbye.github.io copied to clipboard
Shellbye
鸡蛋掉落详解 Super Egg Drop
前几天尝试了一下leetcode中文版通过率最低的一个题（ #41 ），后来发现是关于动态规划的题目，然后听几个人说动态规划是算法题里面比较难的一类，于是就又找了一个动态规划的题目，自己思考了很久，最后依然是通过理解网络上的资源才有了着手之处。
题目
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。 你的目标是确切地知道 F 的值是多少。 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
示例 1：
输入：K = 1, N = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。 如果它没碎，那么我们肯定知道 F = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2：
输入：K = 2, N = 6 输出：3
示例 3：
输入：K = 3, N = 14 输出：4
提示：
1 <= K <= 1001 <= N <= 10000
错误的第一感觉
计算机这个领域，在成为真正的大神之前，大多数人的第一感觉都是不准的，因为这是一个极度理性的领域，至于那些已经封神的大牛，他们几乎已经通过长久的练习与见多识广把很多理性的耗时的分析都转化成了O(1)的感觉。
在最初看这个题目的时候，我的第一反应就是二分查找，简单来看，这个题目就是通过二分查找来确定F的索引，于是第一反应就是logN。但是仔细一看就发现是不对的，那必须啊，因为还有已知条件（K）还没用上呢！根据初高中的理科经验可知，如果题目中有一些已知条件你没用就把题目做完了，那很大概率是你题目做错了（也有可能你是天才）。那么在这个题目中，问题出在哪里呢？这个题目与二分查找不一样的地方在于它的每一次比较大小——即扔鸡蛋——都是有代价的，这种代价就是因为鸡蛋摔破而导致的后面比较机会的减少。下面我就来看看“正确”的解法。
暴力解法
相比上一个题目（ #41 ），这个题目暴力解法也不是很简单就能想到的——起码我是没想到。当然，看过答案之后就会觉得“很明显”了，这样的流程其实是不科学的，下面我就尝试引导读者一步步走向答案。
首先，我们来看扔鸡蛋这个事儿本身，假设在N层的高楼中有K个鸡蛋，这个时候我们在n层扔了一个鸡蛋，那么这一次动作，把整个高楼其实就分成了两部分，一部分是1楼到n楼，这是一个层高为n的新楼，我们暂时叫它一号楼；另一部分是n+1到N楼，这是一栋新产生的层高为N-(n+1)+1=N-n的新楼，我们叫他二号楼。
然后，我们来看刚扔下去的鸡蛋，如果它碎了，说明楼层太高（起码高于F），那么F应该是在一号楼，那么我们就带着剩下的K-1个鸡蛋去一号楼继续，当我们站在一号楼的某一层的时候，其实和最开始是一样的（递归的信号）。如果鸡蛋没碎，说明楼层不够高（低于F），此时我们要去二号楼，但是这里有一点点需要注意的，就是我们在二号楼的某一层的时候，其实该层在原始的楼里是要比当前楼层高n层的，其他同理。
最后，因为我们是要找无论 F 的初始值如何的条件下的查找次数，所以我们要在一号楼和二号楼各自的查找次数中选择那个最大的值，用计算机语言描述整个过程，就是
searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) )
其中的X就是我们刚才扔鸡蛋做在的楼层，它具体是哪一层并不重要。对于从1到N的每一个X，都可以计算出一个对应的searchTime的值，在这N个值中，最小的那个就是本题的答案了！
class Solution {
public int superEggDrop(int K, int N) {
return Solution.recursive(K, N);
}
public static int recursive(int K, int N) {
if (N == 0 || N == 1 || K == 1) {
return N;
}
int minimun = N;
for (int i = 1; i <= N; i++) {
int tMin = Math.max(Solution.recursive(K - 1, i - 1), Solution.recursive(K, N - i));
minimun = Math.min(minimun, 1 + tMin);
}
return minimun;
}
}
上面的这个方法有多暴力呢？通过推导式我们发现它和斐波那契数列第N项的计算方法（Fib(n) = Fib(n-1) + Fib(n-2)）类似，那么，这个东西的时间复杂度又怎么计算呢？对于第N项 Fib(n) = Fib(n-1) + Fib(n-2)，这个计算本身就是一个加法，其时间复杂度是O(1)，但是其中包含了第N-1和第N-2两项，他们又同理本身需要一个O(1)，且也分别包含了第N-1-1、第N-1-2和第N-2-1、第N-2-2四项，以此类推，这就是一个满二叉树的节点总数求和（如图），即O(2^n)，同样的，其空间复杂度很低，仅仅是O(1)。
空间换时间解法
上面的计算之所以时间复杂度高，与递归版本的斐波那契数列一样，就是因为重复计算了很多遍底部节点的值，为了加快这个计算过程，一个简单的提升方法就是拿空间换时间，把计算的中间结果都存储起来，后面直接查表即可。
class Solution {
public int superEggDrop(int K, int N) {
int[][] middleResults = new int[K + 1][N + 1];
for (int i = 1; i <= N; i++) {
middleResults[1][i] = i; // only one egg
middleResults[0][i] = 0; // no egg
}
for (int i = 1; i <= K; i++) {
middleResults[i][0] = 0; // zero floor
}
for (int k = 2; k <= K; k++) { // start from two egg
for (int n = 1; n <= N; n++) {
int tMinDrop = N * N;
for (int x = 1; x <= n; x++) {
tMinDrop = Math.min(tMinDrop, 1 + Math.max(middleResults[k - 1][x - 1], middleResults[k][n - x]));
}
middleResults[k][n] = tMinDrop;
}
}
return middleResults[K][N];
}
}
这个解法利用了一个二维数组存储了部分计算结果（空间复杂度O(KN)），使得时间复杂度降低到了O(KN^2)。但是依然是一个平方级别的时间复杂度，不够快，还能优化吗？
基于二分查找的动态规划法
最开始的时候，我们就想到了二分查找，但是因为发现不对，就果断抛弃了，事实上它还是有利用价值的。在上一个O(KN^2)的算法中，我们拿着K个鸡蛋检查了每一个楼层来寻找F，但是事实上这并不是必须的，为什么呢？我们来看我们上面总结的这个递归的等式
searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) )
现在我们令T1 = searchTime(K-1, X-1)，T2 = searchTime(K, N-X)，其中，T1是随着X的增长而增长的，T2是随着X的增长而降低的，如下图
其中蓝色描出来的部分，就是searchTime(K, N)了，我们可以看出来它是局部有序的，所以可以考虑二分查找之！这里有一些与简单二分查找不一样的地方，就是在简单二分查找中，我们拿到输入数组A和它的下标low，high，mid之后，比较大小直接就是用下标读取数组的值A[low] < A[mid]，但是在我们这个二分查找中，这个值是需要依赖与本题逻辑相关的一些计算的，具体看代码
class Solution {
Map<Integer, Integer> cache = new HashMap<>();
public int superEggDrop(int K, int N) {
if (N == 0)
return 0;
else if (K == 1)
return N;
Integer key = N * 1000 + K; // K <= 100
if (cache.containsKey(key))
return cache.get(key);
int low = 1, high = N;
while (low + 1 < high) {
int middle = (low + high) / 2;
int lowVal = superEggDrop(K - 1, middle - 1);
int highVal = superEggDrop(K, N - middle);
if (lowVal < highVal)
low = middle;
else if (lowVal > highVal)
high = middle;
else
low = high = middle;
}
int minimum = 1 + Math.min(
Math.max(superEggDrop(K - 1, low - 1), superEggDrop(K, N - low)),
Math.max(superEggDrop(K - 1, high - 1), superEggDrop(K, N - high))
);
cache.put(key, minimum);
return cache.get(key);
}
}
在while循环中，我们利用了上文中提到的T1和T2的单调性，计算出了它们内部分别的最大值，因为在while循环之后我们是要先取最大值，然后在众多的最大值中取最小值，所以while内部是通过二分查找的思想找到最大值。这个版本的空间复杂度依然是O(KN)，但是因为利用到了二分查找，所以其时间复杂度就降到了O(KNlogN)，这在很多的算法中，已经是一个可以接受的时间复杂度了，只是并不是最优雅的而已。
更快的方法
这个方法是上一个方法的延续，并把时间复杂度从O(KNlogN)降到了O(KN)，下面我们看一下它的思路。
首先令Xa = opt(K,N)是能够找最小移动次数的最小的X，根据上一个方法中我们分析T1和T2的单调性的方法，我们可以再次分析，并可以最终得出opt(K,N)是随着N的增长而增长的，这个我们也可以从下图中看到
随着N的增长，T2在向上移动，他们的交叉点Xa也在向上移动，那么在上一个方法中需要遍历从1到X的循环就可以改成从Xa到X了，因为小于Xa的都找不到最小移动次数。
与上一个方法自顶向下的方法不同，这次的解法是自底向上的，它每次的计算都是会先找到Xa，然后就可以直接计算出结果。
class Solution {
public int superEggDrop(int K, int N) {
// only one egg situation
int[] dp = new int[N + 1];
for (int i = 0; i <= N; ++i)
dp[i] = i;
// two and more eggs
for (int k = 2; k <= K; ++k) {
int[] dp2 = new int[N + 1];
int x = 1; // start from floor 1
for (int n = 1; n <= N; ++n) {
// start to calculate from bottom
// Notice max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1])
// is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).
while (x < n && Math.max(dp[x - 1], dp2[n - x]) > Math.max(dp[x], dp2[n - x - 1]))
x++;
// The final answer happens at this x.
dp2[n] = 1 + Math.max(dp[x - 1], dp2[n - x]);
}
dp = dp2;
}
return dp[N];
}
}
这里需要特别注意一下dp，在for循环中，它代表是上一次循环解出来的最小值，也就是比当前楼层低一层的情况下的最优解。所以while条件中的
max(dp[x - 1], dp2[n - x]) > max(dp[x], dp2[n - x - 1])，
带入T1 =dp(K−1,X−1)，T2 =dp(K,N−X)，就会发现其实是
max(T1(x-1), T2(x-1)) > max(T1(x), T2(x))（ 🤔）。
换个思路
上面的方法的思路，都还是顺着题目的思路的进行的，其实我们可以换一个思路来想：“求k个鸡蛋在m步内可以测出多少层”。我们令dp[k][m]表示k个鸡蛋在m步内可以测出的最多的层数，那么当我们在第X层扔鸡蛋的时候，就有两种情况：
- 鸡蛋碎了，我们少了一颗鸡蛋，也用掉了一步，此时测出
N - X + dp[k-1][m-1]层，X和它上面的N-X层已经通过这次扔鸡蛋确定大于F； - 鸡蛋没碎，鸡蛋的数量没有变，但是用掉了一步，剩余
X + dp[k][m-1]，X层及其以下已经通过这次扔鸡蛋确定不会大于F；
也就是说，我们每一次扔鸡蛋，不仅仅确定了下一次扔鸡蛋的楼层的方向，也确定了另一半楼层与F的大小关系，所以在下面的关键代码中，使用的不再是max，而是加法（这里是重点）。评论里有人问到为什么是相加，其实这里有一个惯性思维的误区，上面的诸多解法中，往往求max的思路是“两种方式中较大的那一个结果”，其实这里的相加，不是鸡蛋碎了和没碎两种情况的相加，而是“本次扔之后可能测出来的层数 + 本次扔之前已经测出来的层数”。
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K + 1][N + 1];
for (int m = 1; m <= N; m++) {
dp[0][m] = 0; // zero egg
for (int k = 1; k <= K; k++) {
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
if (dp[k][m] >= N) {
return m;
}
}
}
return N;
}
}
这个算法的空间复杂度没有啥疑问，就是O(KN)，关于时间复杂度，原文说是O(KlogN)，但是说实话我还没完全搞懂为啥，因为在我看来两层循环一个K，一个N，应该是O(KN)才对呀，如果有人知道这个是什么回事，还麻烦赐教下了。
参考资料
- https://brilliant.org/wiki/egg-dropping/
- https://leetcode.com/articles/super-egg-drop/
- https://cs.stackexchange.com/questions/39925/finding-the-time-complexity-of-fibonacci-sequence
- https://www.cnblogs.com/Phantom01/p/9490508.html
我觉得，对于换个思路中的解法，应该是因为 dp[k][m] >= N 这个循环终止条件，所以最后外循环不一定需要完全循环到N，就会返回结果了，所以时间复杂度不会是O(KN） 至少是<= O(KN)。
@Shellbye
还有一种写法,空间复杂度只有O(K),时间复杂度O(KlogN)
vector<int> dp(K + 1, 0);
int m;
for (m = 0; dp[K] < N; m++)
for (int k = K; k > 0; --k)
dp[k] += dp[k - 1] + 1;
return m;
@Shellbye 还有一种写法,空间复杂度只有
O(K),时间复杂度O(KlogN)vector<int> dp(K + 1, 0); int m; for (m = 0; dp[K] < N; m++) for (int k = K; k > 0; --k) dp[k] += dp[k - 1] + 1; return m;
@PINK-FL0YD 说实话没看懂你的这个解法为啥是正确的，既然你只用到了一维，那dp在创建的时候就不用非搞成二维的吧
只是把dp矩阵中二维元素换成了次数s
dp[k][s] = d[k][s-1] + dp[k-1][s-1] + 1;
简化掉s用一维数组保存对应的数据,就是
dp[k] = dp[k] + dp[k-1] + 1;
只是把dp矩阵中二维元素换成了次数s
dp[k][s] = d[k][s-1] + dp[k-1][s-1] + 1;简化掉s用一维数组保存对应的数据,就是
dp[k] = dp[k] + dp[k-1] + 1;
为什么可以简化掉s呢？
最后一种做法： 1.鸡蛋碎了，测出N - X + dp[k-1][m-1]层 2.没碎，测出X + dp[k][m-1]层 为什么状态转移方程是：dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1 可以再详细解释一下相加的含义以及+1的含义吗？
最后一种做法： 1.鸡蛋碎了，测出N - X + dp[k-1][m-1]层 2.没碎，测出X + dp[k][m-1]层 为什么状态转移方程是：dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1 可以再详细解释一下相加的含义以及+1的含义吗？
这个相加，并不是说是两种情况加起来的意思，而是未来可能测出来的数量 + 已经测出来的数量，+1表示本层
既然结果是不确定的，那么为什么不是得到当前最多能测出的层数呢？也就是说状态方程为什么不是： dp[k][m] = max(dp[k][m - 1] , dp[k - 1][m - 1]) + 1 ?
@DaDaDoDoLee
既然结果是不确定的，那么为什么不是得到当前最多能测出的层数呢？也就是说状态方程为什么不是： dp[k][m] = max(dp[k][m - 1] , dp[k - 1][m - 1]) + 1 ?
我在原文中加了点说明，这里不是两种情况的比较，而是其中一种情况的计算
应该这么理解，F(t,k) 要求一定要测出 N层，思考如果要达到这个目标，丢下的第X层如何选择，就是要保证如果鸡蛋碎了，比X低的层数一定要能够用F(t-1,k-1)确定出来，如果鸡蛋没碎，比X高的层数一定要能够用F(t-1,k)确定出来，再加上本层，就是能够确定的最大层数
@njulzb
应该这么理解，F(t,k) 要求一定要测出 N层，思考如果要达到这个目标，丢下的第X层如何选择，就是要保证如果鸡蛋碎了，比X低的层数一定要能够用F(t-1,k-1)确定出来，如果鸡蛋没碎，比X高的层数一定要能够用F(t-1,k)确定出来，再加上本层，就是能够确定的最大层数
反过来理解的话是这样的
" 这里需要特别注意一下dp，在for循环中，它代表是上一次循环解出来的最小值，也就是比当前楼层低一层的情况下的最优解。所以while条件中的 max(dp[x - 1], dp2[n - x]) > max(dp[x], dp2[n - x - 1])， 带入T1 =dp(K−1,X−1)，T2 =dp(K,N−X)，就会发现其实是 max(T1(x-1), T2(x-1)) > max(T1(x), T2(x))（ thinking）。 "
这段描述有点晦涩， max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)) 改成 max(T1(x), T2(x)) > max(T1(x+1), T2(x+1))， 这样代入，会好理解一些，代入之后也完全能匹配起来了。
应该这么理解，F(t,k) 要求一定要测出 N层，思考如果要达到这个目标，丢下的第X层如何选择，就是要保证如果鸡蛋碎了，比X低的层数一定要能够用F(t-1,k-1)确定出来，如果鸡蛋没碎，比X高的层数一定要能够用F(t-1,k)确定出来，再加上本层，就是能够确定的最大层数
不对啊，只需要用max(F(t-1,k-1), F(t-1,k))+1就可以确定了，因为只要是二者中的最大值都可以去测任何一边的楼层，用不着相加。
只是把dp矩阵中二维元素换成了次数s
dp[k][s] = d[k][s-1] + dp[k-1][s-1] + 1;简化掉s用一维数组保存对应的数据,就是
dp[k] = dp[k] + dp[k-1] + 1;为什么可以简化掉
s呢？
因为他把二维数组变成了一维的，每次操作都是重复在一维上覆盖而已，相当于只保存了第一列。
刚开始做这个题就用的最暴力的那种方法，结果N取到50就算不出来了，看了K和N的范围简直怀疑人生，看了评论区简洁的答案更怀疑人生了。。。感谢老哥救我一命哈哈哈
关于另一种思路的理解应该是这样的: dp[k][m]表示有k个鸡蛋走m步最多可以(一定能)测出的楼层数 第一步应该在哪层扔鸡蛋?一个正确的选择是在dp[k-1][m-1]+1层开始丢鸡蛋, 分两种情况讨论 第一,如果蛋碎了,那么我们一定能用k-1个鸡蛋用m-1步测出下面的dp[k-1][m-1]层楼,这种情况下,我们总共可以测出无限高的楼层. 第二,如果蛋没碎,显然结果不在下面的dp[k-1][m-1]层楼中,此时我们还有k个蛋和m-1步,那么我们去dp[k-1][m-1]+1以上的楼层继续测试,问题规模变小了,最多可以测出上面的dp[k][m-1]层楼. 那么总共可以测出dp[k-1][m-1]+dp[k][m-1]+1层楼. 显然两种情况应该取较小的,因为我们并不能总是测出无限高的楼.其实最最关键的是理解第一步楼层选择为什么是正确的,严格的证明还是有点难度的.
为什么是+ 而不是取max，因为之前的思路是 K个鸡蛋测N层楼最坏情况下需要移动多少次， 与之相对的应该用 k个鸡蛋移动m次数最好情况下能测多少层。 假设你拥有k个鸡蛋m移动次数，直接来到f(k-1, m-1)+1层（注意这里的f不再表示移动次数，f表示的是楼层数量），事实上这一层就是我们选取的X。扔下鸡蛋最好的情况是什么？下楼是已知的不必再测，最好就是鸡蛋没碎，往上还能测f(k, m-1))层。
作者：fghong 链接：https://www.jianshu.com/p/2f06a3eb953c 来源：简书 简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
关于另一种思路的理解应该是这样的: dp[k][m]表示有k个鸡蛋走m步最多可以(一定能)测出的楼层数 第一步应该在哪层扔鸡蛋?一个正确的选择是在dp[k-1][m-1]+1层开始丢鸡蛋, 分两种情况讨论 第一,如果蛋碎了,那么我们一定能用k-1个鸡蛋用m-1步测出下面的dp[k-1][m-1]层楼,这种情况下,我们总共可以测出无限高的楼层. 第二,如果蛋没碎,显然结果不在下面的dp[k-1][m-1]层楼中,此时我们还有k个蛋和m-1步,那么我们去dp[k-1][m-1]+1以上的楼层继续测试,问题规模变小了,最多可以测出上面的dp[k][m-1]层楼. 那么总共可以测出dp[k-1][m-1]+dp[k][m-1]+1层楼. 显然两种情况应该取较小的,因为我们并不能总是测出无限高的楼.其实最最关键的是理解第一步楼层选择为什么是正确的,严格的证明还是有点难度的.
为什么在蛋碎了的情况下，能测出无限高楼层呢？是因为第一步是随便选择的，这个值可以无限大吗？如果我推断不对，能否给下你推断的理由呀。感谢！
第一步的选择是在dp[k-1][m-1]+1层，如果蛋在这层碎了，那么无论上面还有多少层，都是这个结果，所以可以测出无限层
---原始邮件--- 发件人: "quanyun wei"[email protected] 发送时间: 2019年6月9日 17:55:35 收件人: "Shellbye/Shellbye.github.io"[email protected]; 抄送: "xujiasci"[email protected];"Comment"[email protected]; 主题: Re: [Shellbye/Shellbye.github.io] 鸡蛋掉落详解 Super Egg Drop (#42)
关于另一种思路的理解应该是这样的: dp[k][m]表示有k个鸡蛋走m步最多可以(一定能)测出的楼层数 第一步应该在哪层扔鸡蛋?一个正确的选择是在dp[k-1][m-1]+1层开始丢鸡蛋, 分两种情况讨论 第一,如果蛋碎了,那么我们一定能用k-1个鸡蛋用m-1步测出下面的dp[k-1][m-1]层楼,这种情况下,我们总共可以测出无限高的楼层. 第二,如果蛋没碎,显然结果不在下面的dp[k-1][m-1]层楼中,此时我们还有k个蛋和m-1步,那么我们去dp[k-1][m-1]+1以上的楼层继续测试,问题规模变小了,最多可以测出上面的dp[k][m-1]层楼. 那么总共可以测出dp[k-1][m-1]+dp[k][m-1]+1层楼. 显然两种情况应该取较小的,因为我们并不能总是测出无限高的楼.其实最最关键的是理解第一步楼层选择为什么是正确的,严格的证明还是有点难度的.
为什么在蛋碎了的情况下，能测出无限高楼层呢？是因为第一步是随便选择的，这个值可以无限大吗？如果我推断不对，能否给下你推断的理由呀。感谢！
— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.
首先感谢题主的解法以及大家的评论，从中获益匪浅。因此特整理一下关于“另一种思路”的理解，如果你对 为什么使用加法而不是max？ 有所疑惑，这篇评论或许能帮到你。
dp[k][m] 表示用 k 个鸡蛋移动 m 步可以“保证求解”的最大楼层数。
我们先解释一下这句话中的几个概念：
所谓“求解”，意思就是给定楼层 N，我们能否找到临界楼层 F(F <= N)，使得鸡蛋从 F 层掉落刚好不会被摔碎。所谓“保证求解”，意思就是即使每次丢鸡蛋的结果都很差，最终仍能求解。
比如，给定 1 个鸡蛋移动 1 步，那么可以求解的最大楼层数为 1，即从 1 楼丢下，如果鸡蛋碎了，求得 F=0，如果鸡蛋没碎，求得 F=1。在这种情况下，假如我们给出一个 2 层的楼，就无法保证求解了，因为无论从哪一层丢出鸡蛋，都没有十足的把握能够一次求得 F，换句话说，虽然我们仍有一定的机会能够求解，但无法“保证求解”。
下面回到正题：
假设我们有 k 个鸡蛋可以移动 m 步，考虑某一步 t 应该在哪一层丢鸡蛋？一个正确的选择是在 dp[k-1][t-1] + 1 层丢鸡蛋，结果分两种情况：
-
如果鸡蛋碎了，我们首先排除了该层以上的所有楼层（不管这个楼有多高），而对于剩下的 dp[k-1][t-1] 层楼，我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下，我们总共可以求解无限高的楼层。可见，这是一种非常好的情况，但并不总是发生。
-
如果鸡蛋没碎，我们首先排除了该层以下的 dp[k-1][t-1] 层楼，此时我们还有 k 个蛋和 t-1 步，那么我们去该层以上的楼层继续测得 dp[k][t-1] 层楼。因此这种情况下，我们总共可以求解 dp[k-1][t-1] + dp[k][t-1] + 1 层楼。
容易想象，在所有 m 步中只要有一次出现了第一种情况，那么我们就可以求解无限高的楼层。但“保证求解”的定义要求我们排除一切运气成分，因此我们只得认为每次移动都遇到第二种情况。于是得到递推公式：
dp[k][t] = dp[k-1][t-1] + dp[k][t-1] + 1
基本的问题已经解决了，但是我们还遗留了一个问题：为什么要选择在 dp[k-1][t-1] + 1 层丢鸡蛋？
现在我们已经知道，如果我们每一步都在 dp[k-1][t-1] + 1 层丢鸡蛋，最终是一定能够求解的。但如果我们选择在更低的层或者更高的层丢鸡蛋会怎样呢？我们分两种情况讨论：
-
在更低的楼层丢鸡蛋。同样能够“保证求解”，但最终得到的并不是“最大”楼层数，我们没有充分挖掘鸡蛋数和移动次数的潜力，最终求解时会剩余一定量的鸡蛋或移动次数。
-
在更高的楼层丢鸡蛋。不妨假设高了一层，即在第 dp[k-1][t-1] + 2 层丢鸡蛋。如果鸡蛋碎掉了，我们仍然可以排除该层以上的所有楼层（不管这个楼有多高），但接下来就不好办了，因为我们剩下的 k-1 个鸡蛋在 t-1 步内只能“保证求解” dp[k-1][t-1] 的楼层，而现在剩余的楼层却是 dp[k-1][t-1] + 1，多了一层，因此无法“保证求解”！
综上，我们用排除法证明了每一步都应该在第 dp[k-1][t-1] + 1 层丢鸡蛋。
