Egg Drop Problem

Two condition

1. Egg will break on the x floor than above that floor will also broke
2. If Egg not break on x floor then below that floor will also not break

Above condition will get max floors . from that maximum floors get min value.

min= Interger.Max;
x = 0 to k
max = Max(f(x-1,n-1), f(k-x, n))
if max < min
min = max

k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trials needed to find the critical floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
 x in {1, 2, ..., k}}

Recursion

public static int eggDropRecursive(int k, int n) {
  int min = Integer.MAX_VALUE;

  if (k == 0 || k == 1) {
    return k;
  }

  if (n == 1) {
    return k;
  }

  for (int x = 1; x <= k; x++) {
    int max = Math.max(eggDropRecursive(x - 1, n - 1), eggDropRecursive(k - x, n));
    if (max < min) {
      min = max;
    }
  }

  return min + 1;
}

Dynamic Programming

private static int eggDropRecursiveDp(int numberOfFloor, int noOfEgg) {
  int dp[][] = new int[noOfEgg + 1][numberOfFloor + 1];

  for (int i = 1; i <= numberOfFloor; i++) {
    dp[1][i] = i;
  }
  for (int i = 1; i <= noOfEgg; i++) {
    dp[i][1] = 1;
    dp[i][0] = 0;
  }
   
  for (int i = 2; i <= noOfEgg; i++) {
    for (int j = 2; j <= numberOfFloor; j++) {
      dp[i][j] = Integer.MAX_VALUE;
      for (int x = 1; x <= j; x++) {
        int eggBroke = dp[i - 1][x - 1];
        int eggNotBroke = dp[i][j - x];
        int max = 1 + Math.max(eggBroke, eggNotBroke);
        if (max < dp[i][j]) {
          dp[i][j] = max;
        }
      }
    }
  }
  return dp[noOfEgg][numberOfFloor];
}