# 887     Super Egg Drop

## 887. [Super Egg Drop](https://leetcode.com/problems/super-egg-drop/description/)

## 1. Question

You are given`K`eggs, and you have access to a building with`N`floors from`1`to`N`.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor`F`with`0 <= F <= N`such that any egg dropped at a floor higher than`F`will break, and any egg dropped at or below floor`F`will not break.

Each*move*, you may take an egg (if you have an unbroken one) and drop it from any floor`X`(with `1 <= X <= N`).

Your goal is to know **with certainty** what the value of`F`is.

What is the minimum number of moves that you need to know with certainty what`F`is, regardless of the initial value of`F`?

**Example 1:**

```
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
```

**Example 2:**

```
Input: K = 2, N = 6
Output: 3
```

**Example 3:**

```
Input: K = 3, N = 14
Output: 4
```

**Note:**

1. `1 <= K <= 100`
2. `1 <= N <= 10000`

## 2. Implementation

**(1) Memoization**

```
```

**(2) Memoization + Binary Search**

思路:

```java
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] cache = new int[N + 1][K + 1];

        for (int[] row : cache) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        return getMinMoves(N, K, cache);
    }

    public int getMinMoves(int floors, int eggs, int[][] cache) {
        if (floors <= 1) {
            return floors;
        }

        if (eggs <= 0) {
            return 0;
        }

        if (eggs == 1) {
            return floors;
        }

        if (cache[floors][eggs] != Integer.MAX_VALUE) {
            return cache[floors][eggs];
        }

        int start = 1, end = floors;
        int minMoves = Integer.MAX_VALUE;
        // broken is increasing with floors
        // unbroken is decreasing with floors
        // in order minimize Math.max(broken, unbroken), we use to binary search to find the smallest floor, that
        // make broken >= unbroken
        while (start <= end) {
            int mid = start + (end - start) / 2;

            int broken = getMinMoves(mid - 1, eggs - 1, cache);
            int unbroken = getMinMoves(floors - mid, eggs, cache);

            minMoves = Math.min(minMoves, 1 + Math.max(broken, unbroken));

            if (broken == unbroken) {
                break;
            }
            else if (broken < unbroken) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        cache[floors][eggs] = minMoves;
        return minMoves;
    }
}
```

**(3) DP**

```java
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[N + 1][K + 1];
        int moves = 0;
        while (dp[moves][K] < N) {
            ++moves;
            for (int k = 1; k <= K; k++) {
                dp[moves][k] = dp[moves - 1][k - 1] + dp[moves - 1][k] + 1; 
            }
        }
        return moves;
    }
}
```

## 3. Time & Space Complexity

**(1) Memoization:** 时间复杂度O(K \* N^2), 空间复杂度O(KN)

**(2) Memoization + Binary Search:** 时间复杂度O(K \* N\* logN), 空间复杂度O(KN)

**(3) DP:** 时间复杂度O(KlogN), 空间复杂度O(KN)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/887-super-egg-drop.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.