刷题使我快乐，满脸开心.jpg
- 来源：力扣（LeetCode）
- 链接：https://leetcode.cn/problems/super-egg-drop/
- 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 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 <= 10^4
思路
这道题是曾经 Google 的面试题，很经典。
首先声明下，这道题比较困难，我个人解出这道题带有 运气和经验 成分，状态转移方程虽然对了，但是总感觉自己的证明过程是有些问题的。
思路上跟这位大佬最后办法的思路是基本一样的，但是状态转移方程解释上不一样。
所以发下这篇详解，大家可以移步细看
类似思路详解
动态规划
这道题一开始看到，很容易往二分法的方向上去思考，但是其实只用二分法并不能很好的解出这道题，可以配合动态规划完成求解。
不过我的思路是受其他题目的启发，做了一个转换：
与其求 k 个鸡蛋、n 层楼的条件下，需要几步
不如求 k 个鸡蛋、n 步的条件下，能确定几层楼
- 所以
dp[i][j]含义为i个鸡蛋，j步内可以测出的最大楼层数 dp[0][j]一定是0- 状态转移方程比较难想：
条件是
i个鸡蛋j步
我们不确定下一次扔鸡蛋碎不碎，所以从dp[i-1][j-1] + 1处开始扔
因为在dp[i-1][j-1] + 1处扔鸡蛋，可以稳定的确定dp[i-1][j-1] + 1层
如果碎了，那我们在需要找到f值的情况下，可以测出的最大楼层数就是dp[i-1][j-1] + 1
如果没碎，那我们可以继续测试，再测出i个鸡蛋，j-1步数下可以测到的最高楼层数
所以得到了转移方程dp[i][j] = dp[i-1][j-1] + 1 + dp[i][j-1]
思路大体就是这些，具体看代码，细节在注释了～
代码
func superEggDrop(k int, n int) int {
// dp[i][j]含义为 i 个鸡蛋，j 步内可以测出的最大楼层数
dp := make([][]int, k+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 步数
for j:=1; j<=n; j++ {
// 0个鸡蛋时，只能保障测出0步
dp[0][j] = 0
// 鸡蛋数
for i:=1; i <= k; i++ {
// 当前共 i 个鸡蛋 j 步数
// 在 dp[i-1][j-1] + 1 处扔鸡蛋，可以稳定的确定 dp[i-1][j-1] + 1 层
// 如果碎了，其实我们可以排出楼上所有楼层，正无穷
// 如果没碎，那我们可以继续保持 i 个鸡蛋，测的 j-1 步数下可以测到的最高楼层
// 所以 dp[i][j] = dp[i-1][j-1] + 1 + dp[i][j-1]
dp[i][j] = dp[i-1][j-1] + 1 + dp[i][j-1]
// 步数在外层，鸡蛋在内层，所以楼层大于 n 时，一定是最小所需的步数
if dp[i][j] >= n {
return j
}
}
}
// 一层层往上测，所需步数
return n
}