Dynamic Programming – Egg Dropping Problem

Objec­tive:  There are n number of eggs and building which has k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break.

Note:

  • One trial is – dropping an egg once from the particular floor.
  • If egg does not break after dropping, will be used again.
  • If egg breaks when dropped from some floor then it will break if dropped from any higher floor.
  • If egg does not break when dropped from some floor then it will not break if dropped from any lower floor.

Approach:

N eggs, k floors

Recursion:  try dropping an egg from each floor from 1 to k and calculate the minimum number of dropping needed in worst case.

  • Base cases –
    • Eggs – 1, floors – x : play safe and drop from floor 1, if egg does not break then drop from floor 2 and so on. So in worst case x times an egg needs to be dropped to find the solution.
    • Floors = 0: No trials are required.
    • Floors = 1: 1 trails is required.
  • For rest of the case, if an egg is dropped from xth floor then there are only 2 outcomes which are possible. Either egg will break OR egg will not break.
    • If Egg breaks – check the floors lower than x. So problem is reduced is n-1 eggs and x-1 floors.
    • If egg does not break – check the floors higher than x floors with all the n eggs are remaining. So problem is reduced to n eggs and k-x floors.

Recursive Equation

n eggs, k floors

getDrops (n, k) – given n eggs and k floor building, minimum of drops to determine the floor from which egg does not break if dropped.

getDrops (n, k) = 1 + Min(x = 1,2,….k)[(drops(n-1, k-1), drops(n, k-x)]

Code:

public class EggDropRecursion {
public int getDrops(int eggs, int floors){
//base case 1:
//if floors = 0 then no drops are required OR floors = 1 then 1 drop is required
if(floors==0 || floors==1)
return floors;
//base case 2:
//if only one egg is there then drops = floors
if(eggs==1)
return floors;
int minimumDrops=Integer.MAX_VALUE, tempResult;
//check dropping from all the floors 1 to floors and pick the minimum among those.
//for every drop there are 2 scenarios – a) either egg will break b) egg will not break
for (int i = 1; i <=floors ; i++) {
//for the worst case pick the maximum among a) and b)
tempResult = Math.max(getDrops(eggs1,i1), getDrops(eggs, floorsi));
minimumDrops = Math.min(tempResult,minimumDrops);
}
return minimumDrops + 1;
}
public static void main(String[] args) {
EggDropRecursion eggDropRecursion = new EggDropRecursion();
int eggs = 2;
int floors = 10;
System.out.printf("(Recursion) Minimum number of drops required in worst case with eggs:
" + eggs + " and floors:" + floors + " is: " + eggDropRecursion.getDrops(eggs,floors));
}
}


Output:

(Recursion) Minimum number of drops required in worst case with eggs: 2 and floors: 10 is: 4

Time Complexity: 2k

If we look closely we are solving many subproblems repeatedly.

Dynamic Programming: Bottom-up

  • Solve it in bottom up manner, means start from the smallest sub problem possible (here it is 0 eggs 0 floors) and solve it. Store the result in some temporary storage.
  • Recursive equation will be same as above. Start solving from smallest sub problem and move towards final problem. Use the temporary result being stored instead of solving the sub problems again.
  • See the code for more understanding.

Time Complexity: nk2

Code:

public class EggDroppDP {
public int getDrops(int eggs, int floors){
int [][] eggDrops = new int [eggs+1][floors+1];
//base case 1:
//if floors = 0 then no drops are required // OR floors = 1 then 1 drop is required
for (int i = 1; i <=eggs ; i++) {
eggDrops[i][0] = 0;
eggDrops[i][1] = 1;
}
//base case 2:
//if only one egg is there then drops = floors
for (int i = 1; i <=floors ; i++) {
eggDrops[1][i] = i;
}
for (int i = 2; i <=eggs ; i++) {
for (int j = 2; j <=floors ; j++) {
eggDrops[i][j] = Integer.MAX_VALUE;
int tempResult;
for (int k = 1; k <=j ; k++) {
tempResult = 1 + Math.max(eggDrops[i1][k1], eggDrops[i][jk]);
eggDrops[i][j] = Math.min(tempResult,eggDrops[i][j]);
}
}
}
// eggDrops[eggs][floors] will have the result : minimum number of drops required in worst case
return eggDrops[eggs][floors];
}
public static void main(String[] args) {
EggDroppDP eggDP = new EggDroppDP();
int eggs = 2;
int floors = 100;
System.out.printf("(DP) Minimum number of drops required in worst case with eggs:
%s and floors: %s is : %s",eggs,floors,eggDP.getDrops(eggs,floors));
}
}

view raw
EggDroppDP.java
hosted with ❤ by GitHub

Output:

(DP) Minimum number of drops required in worst case with eggs: 2 and floors: 100 is : 14

Reference: http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle