这是经典的 鸡蛋掉落问题，LeetCode 887，我直接给你最优 DP + 二分写法（Java 版），能 AC，时间复杂度 O(k·n·logn)，空间 O(k·n)。

思路

• 定义  dp[i][j] ： i  个鸡蛋， j  层楼，确定临界层最少需要扔多少次
• 转移：在第  x  层扔
• 碎了： dp[i-1][x-1]
• 没碎： dp[i][j-x]
• 最坏情况： max(dp[i-1][x-1], dp[i][j-x]) + 1
• 对每个  j ，用二分找最优 x，把枚举从 O(n) 降到 O(logn)

Java 代码（可直接提交）

java

public class Solution {
public int superEggDrop(int k, int n) {
// dp[i][j] = i个鸡蛋，j层楼，最少次数
int[][] dp = new int[k + 1][n + 1];

    // 1个鸡蛋
    for (int j = 1; j <= n; j++) {
        dp[1][j] = j;
    }
    // 0层或1层
    for (int i = 1; i <= k; i++) {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }

    for (int i = 2; i <= k; i++) {
        for (int j = 2; j <= n; j++) {
            int left = 1, right = j;
            int res = Integer.MAX_VALUE;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int broken = dp[i-1][mid-1];
                int notBroken = dp[i][j-mid];
                if (broken < notBroken) {
                    res = Math.min(res, notBroken + 1);
                    left = mid + 1;
                } else {
                    res = Math.min(res, broken + 1);
                    right = mid - 1;
                }
            }
            dp[i][j] = res;
        }
    }
    return dp[k][n];
}

}

更快的数学反推版（O(k·logn)）

面试加分项：用**“t次操作、k个鸡蛋最多能测多少层”**反推最小 t

java

public int superEggDrop(int k, int n) {
int left = 1, right = n;
int ans = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(k, mid, n)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}

// t次操作，k个鸡蛋，能否覆盖n层
private boolean check(int k, int t, int n) {
long sum = 0;
long cur = 1;
for (int i = 1; i <= k; i++) {
cur = cur * (t - i + 1) / i;
sum += cur;
if (sum >= n) return true;
}
return sum >= n;
}

你要我帮你把这道题的DP 推导过程、二分为什么正确、边界条件一步步讲清楚吗？