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].
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].
