# 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)