4

Solution

Method 1 - Naive Recursion (Exponential)

Intuition

Brute-force every possible first drop floor x (1..h). For each x we consider two outcomes: egg breaks (search below with one fewer egg) or egg survives (search above with same eggs). We take the worse (max) because we require certainty, then choose the x that minimizes this worst-case.

Approach

Define f(e,h) recursively with base cases.
Enumerate all x.
Return the minimum worst-case cost.

Recurrence

f(1,h) = h
f(e,0) = 0, f(e,1) = 1
f(e,h) = 1 + min_{1<=x<=h} max( f(e-1, x-1), f(e, h-x) )

Code

C++

class SolutionNaive {
public:
    int superEggDrop(int k, int n) { return

Related Tags

Continue Practicing