Egg Drop Problem | Dynamic Programming | C++ Solution
Egg Drop Problem, is a Dynamic Programming related problem and in this post we will see how we can solve this challenge in C++
Given 'n' eggs and 'k' floors,find the min number of attempts/drops to find the floor from lowest floor from which if the egg is dropped then it will break. If there is only 1 egg and k floors then we need to drop it from the 1st floor till the floor from which when dropped it breaks If we are given 'n' eggs and 'k' floors then we check for each and every floor two cases can arrive for the x floor:
Either the egg will break, so recurse for lower floors :n-1,x-1
The egg doesn't break then we need to look for the k-x floors with n eggs
Now since for each floor we don't know whether the egg will break or not so we have to consider both cases of the floors above and below it. Now since we need the worst case so for both of the cases ,we can get the worst by taking MAX of both. Do this for all k floors and return MIN( all worst cases)
Please check the main.cpp snippet for the solution.
This solution originally posted at: Github by @susantabiswas