44 Egg Dropping Problem Memoization

Egg Dropping using Memoization(Dynamic Programming)

Problem statement: You are given N floor and K eggs. You have to minimize the number of times you have to drop the eggs to find the critical floor where critical floor means the floor beyond which eggs start to break. Assumptions of the problem:

If egg breaks at ith floor then it also breaks at all greater floors.
If egg does not break at ith floor then it does not break at all lower floors.
Unbroken egg can be used again.
Note: You have to find minimum trials required to find the critical floor not the critical floor.

Example:
Input:
4
2

Output:
Number of trials when number of eggs is 2 and number of floors is 4: 3

------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:

PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[aryansinha]

The one who droped directly at video 43,
*When comes why memoization* : Ohh WOW!! nice explaination what a nice guy, no one teaches like that, THE LEGEND!
*The guy watching from video 1*
When comes why memoization : Not again.. ahhh. NO.. Ohh lets hear him maybe we could learn something NO NOT AGAIN!!!..

[amanbhadauria]

those who know why memoization needed start at 12:32

[navaugustt]

Thanks buddy ❤️ finally i have some command over Dp, Completed the playlist with full enthusiasm and knowledge gathering. #Dpwithadityaverma ❤️

[anuragshakya]

No Dislikes, I think Tushar Roy has not watched this video yet.

[anant]

43 of 50 (86%) done! Nice revision of memoization.

[adityajain]

Can we get the pdf copy of all the pages you write an explanation on? Will be of great help!

[ankoor]

Python: Top Down


eggs = 3
floors = 5
T = [[-1 for _ in range(floors+1)] for _ in range(eggs+1)]


def Solve(eggs, floors):
if floors == 0 or floors == 1:
return floors
if eggs == 1:
return floors
if T[eggs][floors] != -1:
return T[eggs][floors]
count = float('inf')
for i in range(1, floors+1):
temp = 1 + max(Solve(eggs, floors-i), Solve(eggs-1, i-1))
count = min(count, temp)
T[eggs][floors] = count
return count


attempts = Solve(eggs, floors)
print('# of attempts: ', attempts)

[princesaini]

Bhai Its called Top down apporach. Although Its brilliant the way you explain.

[KishankumarPatel]

Even this memorized solution is giving TLE on Leet Code -> Better Solution can be figuring out the max no. of floor that cn be checked with a given no of egg.

[dibyanshujaiswal]

you should have returned 1 + mn as we are making an attempt to check for future conditions.

[madhurbhargava]

Bro, you need to use binary search in place of your for loop, otherwise this will give TLE on lc despite memoization.

[rituraj]

sir, when r u uploading the videoes fibonaci and their 7

[ankoor]

Python: Bottom Up, Time: O(E N^2), Space: O(EN)


def Solve(eggs, floors):

# Initialize T with 0's
T = [[0 for _ in range(floors+1)] for _ in range(eggs+1)]
# If only 1 egg was given
for j in range(floors+1):
T[1][j] = j
for i in range(2, eggs+1): # From 2 because we do not want to overwrite row index 1 values
for j in range(1, floors+1):
T[i][j] = float('inf')
for k in range(1, j+1):
count = 1 + max(T[i-1][k-1], T[i][j-k])
T[i][j] = min(T[i][j], count)
return T[i][j]


eggs = 2
floors = 100
attempts = Solve(eggs, floors)
print('Min # of attempts: ', attempts)

[devashisgupta]

why can't we use hashmap like previous videos for memoization

[tanmaysahare]

Can anybody tell he is live or not just asking for in some previous videos comments someone says he is not live

[arjunkhanna]

Can we use the concept of binary search on answer?

[rahulnagwanshi]

Those two dislikes are from Tushar and Jenny

[TW-ukxi]

What's the time complexity of this optimized code?

[deepanshubhatia]

Bro, I used Recursive and Memoization, However, it is exceeding time limit on LeetCode for Test Case (Egg -> 3, Floors -> 25). I have also memoized inner loop but still getting same issue. Any Help?

[rkalpeshk]

JAVA CODE :

static int funMemo(int egg, int floor, int[][] memo) {
if (floor == 0 || floor == 1)
return floor;

if (egg == 1)
return floor;

if (memo[egg][floor] != -1)
return memo[egg][floor];

int min = Integer.MAX_VALUE;

for (int k = 1; k <= floor; k++) {

int down, top;

if (memo[egg - 1][k - 1] != -1) {
down = memo[egg - 1][k - 1];
} else {
down = funMemo(egg - 1, k - 1, memo);
}

if (memo[egg][floor - k] != -1) {
top = memo[egg][floor - k];
} else {
top = funMemo(egg, floor - k, memo);
}

int temp = 1 + Math.max(down, top);

if (min > temp)
min = temp;
}
memo[egg][floor] = min;
return min;
}