Egg Dropping problem

"""
Intuition for Egg Dropping Problem (Step-by-Step Breakdown)

Step 1: Identify the Problem Type
---------------------------------
We are given 'e' eggs and 'f' floors. We need to find the MINIMUM number
of attempts needed in the WORST CASE to find the threshold floor (the
highest floor from which an egg doesn't break). Because we are looking
for an optimal strategy amidst uncertainty, this falls under the
Matrix Chain Multiplication (MCM) pattern of 'partitioning'.

Step 2: Define the Range (The 'k' Loop)
---------------------------------------
In MCM, we split a range [i, j]. Here, our 'range' is the number of
floors. We can choose to drop an egg from any floor 'k' where
1 <= k <= f. This 'k' acts as our partition point.

Step 3: The Base Cases (The 'Small' Problems)
---------------------------------------------
- If floors (f) == 0 or 1: We need 0 or 1 attempts respectively.
- If eggs (e) == 1: We must start from the 1st floor and go up
  sequentially. In the worst case, the threshold is the top floor,
  so we need 'f' attempts.

Step 4: The Recursive 'Worst Case' Logic
-----------------------------------------
When we drop an egg from floor 'k', only two things can happen:

Scenario 1: The Egg BREAKS
   - We now have (e - 1) eggs.
   - We only need to check floors BELOW 'k'.
   - New problem: solve(e - 1, k - 1)

Scenario 2: The Egg DOES NOT BREAK
   - We still have 'e' eggs.
   - We only need to check floors ABOVE 'k' (total f - k floors).
   - New problem: solve(e, f - k)

Step 5: Finding the 'Worst Case' for a Split
---------------------------------------------
Since we want to be certain of our answer regardless of whether the egg
breaks or not, we must consider the WORST of these two scenarios:
Worst Case at floor 'k' = 1 + max(solve(e-1, k-1), solve(e, f-k))
(The '1' represents the current attempt we just made).

Step 6: Minimizing the Attempts
-------------------------------
We repeat this calculation for every possible floor 'k' from 1 to f.
Our final answer is the MINIMUM of all these worst-case values, as we
are looking for the most efficient strategy.
Ans = min(for all k: 1 + max(break, no_break))

Step 7: Optimization (Memoization)
----------------------------------
The recursive tree has many overlapping sub-problems (e.g., calculating
3 eggs and 5 floors multiple times). We use a 2D array or a map
table[e+1][f+1] to store results and avoid TLE (Time Limit Exceeded).

T.C: We are checking on all e eggs and all f floors so e*f states and for each states , work needs to be done is O(f) ie. loop so Total= O(e*f*f)=O(ef^2)
We are storing the e*f states so S.C=O(e*f)
"""


from math import inf
def fun(e,f,dp):
    if e==1:
        return f
    if f<=1:
        return f
    if dp[f][e]!=-1:
        return dp[f][e]
    _min=inf
    for k in range(1,f+1):
        temp=1+ max(fun(e-1,k-1,dp), fun(e,f-k,dp))
        _min=min(temp,_min)
    dp[f][e]=_min
    return dp[f][e]


class Solution:
    def eggDrop(self, e, f):
        dp=[[-1]*(e+1) for _ in range(f+1)]
        return fun(e,f,dp)


#M-2 More optimised approach T.C O(e*f*log(f))
from math import inf

def fun(e, f, dp):

    if e == 1:
        return f

    if f <= 1:
        return f

    if dp[e][f] != -1:
        return dp[e][f]

    low = 1
    high = f

    ans = inf

    while low <= high:

        mid = (low + high) // 2

        break_case = fun(e - 1, mid - 1, dp)
        survive_case = fun(e, f - mid, dp)

        temp = 1 + max(break_case, survive_case)

        ans = min(ans, temp)

        # move towards larger side
        if break_case < survive_case:
            low = mid + 1
        else:
            high = mid - 1

    dp[e][f] = ans

    return ans


class Solution:
    def eggDrop(self, e, f):

        dp = [[-1] * (f + 1) for _ in range(e + 1)]

        return fun(e, f, dp)