> 开始今天的题目前 我们可以先看李永乐老师关于这个问题的讲解 <iframe src="//player.bilibili.com/player.html?aid=96214853&bvid=BV1KE41137PK&cid=164251653&page=1" allowfullscreen="allowfullscreen" width="100%" height="499" scrolling="no" frameborder="0" sandbox="allow-top-navigation allow-same-origin allow-forms allow-scripts"></iframe> # [题目描述](https://leetcode-cn.com/problems/super-egg-drop/)  ## 方法1 动态规划 + 二分查找 先贴个题解吧，我自己确实还不是很理解透，之后有能力会来填坑 ```java import java.util.Arrays; public class Solution { public int superEggDrop(int K, int N) { // dp[i][j]：一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少仍的次数 int[][] dp = new int[N + 1][K + 1]; // 初始化 for (int i = 0; i <= N; i++) { Arrays.fill(dp[i], i); dp[i][0] = 0; dp[i][1] = i; } for (int j = 0; j <= K; j++) { dp[0][j] = 0; dp[1][j] = 1; } dp[1][0] = 0; // 开始递推 for (int i = 2; i <= N; i++) { for (int j = 2; j <= K; j++) { // 在区间 [1, i] 里确定一个最优值 int left = 1; int right = i; while (left < right) { // 找 dp[k - 1][j - 1] <= dp[i - mid][j] 的最大值 k int mid = left + (right - left + 1) / 2; int breakCount = dp[mid - 1][j - 1]; int notBreakCount = dp[i - mid][j]; if (breakCount > notBreakCount) { // 排除法（减治思想）写对二分见第 35 题，先想什么时候不是解 // 严格大于的时候一定不是解，此时 mid 一定不是解 // 下一轮搜索区间是 [left, mid - 1] right = mid - 1; } else { // 这个区间一定是上一个区间的反面，即 [mid, right] // 注意这个时候取中间数要上取整，int mid = left + (right - left + 1) / 2; left = mid; } } // left 这个下标就是最优的 k 值，把它代入转移方程 Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1) 即可 dp[i][j] = Math.max(dp[left - 1][j - 1], dp[i - left][j]) + 1; } } return dp[N][K]; } } ```