Solving Egg Dropping Puzzle

The standard solution for finding the minimum number of drops for N floors and M eggs is already covered on many websites.In this blog , I will cover a different result,i.e,Finding recurrence relation to the  maximum number of floors which can be covered using a given number of eggs and drops.

We have  M eggs, N drops ,
g[m][n] denotes the maximum number of floors which can be covered using the above.

Reccurence Relation:

g[m][n] = g[m-1][n-1] + g[m][n-1] + 1


Base Cases :-

1)g[m][0] = 0           | With 0 drops , 0 floors can be covered

2)g[1][m] = m          | With m drops , 1 egg -> only m floors can be covered.This is because we only have                                     the option of dropping the only egg from 1st floor , if it breaks we are done , else                                           (m-1) floors above can be covered.


Some general solutions:

1)g[2][n] = (n+1)C2
2)g[3][n] = (n+2)C3 and so on...

Explanation:

For m eggs , and n drops 

We know that we can cover g[m-1][n-1] floors using (m-1) eggs and (n-1) drops. Hence we will drop mth egg from (g[m-1][n-1] + 1)th floor , because if the egg drops we are left with (m-1) eggs and (n-1) drops, which can cover g[m-1][n-1] floors(as per definition). Now , if the mth egg doesnt breaks , then we are left with m eggs, (n-1) drops which can cover g[m][n-1] floors , So in total we dropped from (g[m-1][n-1] + 1)th floor, and g[m][n-1] floors above can also be covered, which gives us
g[m][n] = 1 + g[m-1][n-1] + g[m][n-1].