# LeetCode 887: Super Egg Drop

## Problem Restatement

We are given `k` identical eggs and a building with `n` floors.

There is some unknown floor `f` such that:

| Drop floor | Result |
|---|---|
| Floor `<= f` | Egg does not break |
| Floor `> f` | Egg breaks |

We need to determine the exact value of `f`.

Each move lets us drop one unbroken egg from any floor. If the egg breaks, it cannot be used again. If it does not break, we can reuse it.

Return the minimum number of moves needed to determine `f` with certainty in the worst case.

LeetCode gives constraints `1 <= k <= 100` and `1 <= n <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `k`, the number of eggs |
| Input | `n`, the number of floors |
| Output | Minimum number of moves needed in the worst case |
| Goal | Determine the exact critical floor `f` |
| Egg breaks | It cannot be reused |
| Egg survives | It can be reused |

Function shape:

```python
def superEggDrop(self, k: int, n: int) -> int:
    ...
```

## Examples

Example 1:

```text
Input: k = 1, n = 2
Output: 2
```

With only one egg, we must test floors from bottom to top.

Drop from floor `1`.

If it breaks, then `f = 0`.

If it survives, drop from floor `2`.

So we need `2` moves in the worst case.

Example 2:

```text
Input: k = 2, n = 6
Output: 3
```

With two eggs and six floors, three moves are enough.

One possible strategy is to drop from floor `3`.

If it breaks, use one egg to test floors `1` and `2`.

If it survives, test higher floors with the remaining moves.

Example 3:

```text
Input: k = 3, n = 14
Output: 4
```

With three eggs and fourteen floors, four moves are enough.

## First Thought: Try Every First Drop Floor

A direct dynamic programming definition is:

```text
dp[eggs][floors] = minimum moves needed
```

Suppose we choose a first drop floor `x`.

There are two cases.

If the egg breaks, then we have:

```text
eggs - 1 eggs
x - 1 lower floors to check
```

If the egg does not break, then we have:

```text
eggs eggs
floors - x higher floors to check
```

Since we need a worst-case guarantee, the cost of dropping at floor `x` is:

```text
1 + max(
    dp[eggs - 1][x - 1],
    dp[eggs][floors - x]
)
```

Then we minimize this over all possible `x`.

This is correct, but it is too slow if implemented directly, because each state tries many drop floors.

## Problem With the Direct DP

There are roughly:

```text
k * n
```

states.

For each state, trying every first drop floor may cost up to:

```text
n
```

So the direct version can take:

```text
O(k * n^2)
```

With `n = 10^4`, this is too large.

We need a better DP viewpoint.

## Key Insight

Instead of asking:

```text
How many moves do we need for n floors?
```

ask the reverse question:

```text
How many floors can we determine with m moves and k eggs?
```

Define:

```text
dp[eggs][moves] = maximum number of floors we can check with this many eggs and moves
```

Now consider one drop.

If the egg breaks, we can check floors below the drop using:

```text
eggs - 1 eggs
moves - 1 moves
```

That covers:

```text
dp[eggs - 1][moves - 1]
```

floors below.

If the egg does not break, we can check floors above the drop using:

```text
eggs eggs
moves - 1 moves
```

That covers:

```text
dp[eggs][moves - 1]
```

floors above.

The current drop floor itself accounts for `1` more floor.

So:

```text
dp[eggs][moves]
=
dp[eggs - 1][moves - 1]
+ 1
+ dp[eggs][moves - 1]
```

We keep increasing `moves` until:

```text
dp[k][moves] >= n
```

The first such `moves` is the answer.

## Algorithm

Use a one-dimensional DP array:

```python
dp[eggs]
```

where `dp[eggs]` means the maximum number of floors that can be checked with the current number of moves and `eggs` eggs.

Initialize all values to `0`.

Then repeat:

1. Increase `moves` by `1`.
2. Update eggs from `k` down to `1`.
3. Apply the recurrence:

```python
dp[eggs] = dp[eggs] + dp[eggs - 1] + 1
```

The reverse loop is important because `dp[eggs - 1]` must still mean the value from the previous move count.

Stop when:

```python
dp[k] >= n
```

Return `moves`.

## Walkthrough

Use:

```text
k = 2
n = 6
```

Start:

```text
dp = [0, 0, 0]
moves = 0
```

After 1 move:

| Eggs | Floors checkable |
|---|---:|
| 1 | 1 |
| 2 | 1 |

After 2 moves:

| Eggs | Floors checkable |
|---|---:|
| 1 | 2 |
| 2 | 3 |

After 3 moves:

| Eggs | Floors checkable |
|---|---:|
| 1 | 3 |
| 2 | 6 |

Now `dp[2] = 6`, so with 2 eggs and 3 moves we can determine `f` among 6 floors.

Answer:

```python
3
```

## Correctness

Let `dp[e]` after `m` iterations mean the maximum number of floors whose critical floor can be determined using `e` eggs and at most `m` moves.

For `m = 0`, no moves are available, so zero floors can be checked. The initialization is correct.

Now suppose the interpretation is true for `m - 1` moves.

With `e` eggs and `m` moves, choose one floor to drop from.

If the egg breaks, then we have `e - 1` eggs and `m - 1` moves left. By the induction hypothesis, we can handle `dp[e - 1]` floors below the chosen floor.

If the egg survives, then we still have `e` eggs and `m - 1` moves left. By the induction hypothesis, we can handle `dp[e]` floors above the chosen floor.

The chosen floor itself adds one more distinguishable floor.

Therefore, with `e` eggs and `m` moves, we can handle:

```text
previous_dp[e - 1] + 1 + previous_dp[e]
```

floors.

This is exactly the update rule.

The algorithm stops at the first `moves` such that `dp[k] >= n`. At that point, `moves` moves are enough to determine the critical floor among `n` floors. Since we increase `moves` one at a time and stop at the first sufficient value, this number is minimal.

Thus, the algorithm returns the correct minimum worst-case number of moves.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(k * answer)` | For each move count, we update all egg counts |
| Space | `O(k)` | The DP array stores one value per egg count |

Since `n <= 10^4`, the number of moves is small enough for this method.

## Implementation

```python
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        moves = 0

        while dp[k] < n:
            moves += 1

            for eggs in range(k, 0, -1):
                dp[eggs] = dp[eggs] + dp[eggs - 1] + 1

        return moves
```

## Code Explanation

We create a DP array:

```python
dp = [0] * (k + 1)
```

`dp[eggs]` means how many floors we can check with the current number of moves and `eggs` eggs.

The loop continues until we can cover all `n` floors:

```python
while dp[k] < n:
```

Each loop adds one allowed move:

```python
moves += 1
```

Then we update egg counts in reverse:

```python
for eggs in range(k, 0, -1):
```

The recurrence is:

```python
dp[eggs] = dp[eggs] + dp[eggs - 1] + 1
```

Here:

| Term | Meaning |
|---|---|
| `dp[eggs - 1]` | Floors below if the egg breaks |
| `1` | The current drop floor |
| `dp[eggs]` | Floors above if the egg survives |

When `dp[k]` reaches at least `n`, the current `moves` is enough.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.superEggDrop(1, 2) == 2
    assert s.superEggDrop(2, 6) == 3
    assert s.superEggDrop(3, 14) == 4
    assert s.superEggDrop(1, 10) == 10
    assert s.superEggDrop(2, 100) == 14
    assert s.superEggDrop(100, 1) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `k = 1, n = 2` | With one egg, must test linearly |
| `k = 2, n = 6` | Standard example |
| `k = 3, n = 14` | Standard example |
| `k = 1, n = 10` | One egg edge case |
| `k = 2, n = 100` | Larger two-egg case |
| `k = 100, n = 1` | Many eggs, one floor |