Egg Drop With 2 Eggs and N Floors LeetCode solution in Java

1
class Solution {
2
  public int twoEggDrop(int n) {
3
    int egg = 2; // hard coded to 2 eggs for this problem
4
    int[][] dp = new int[n + 1][egg + 1];
5
    return eggDrop(n, egg, dp);
6
  }
7

8
  int eggDrop(int n, int egg, int[][] dp) {
9
    if (n <= 2 || egg == 1) return n;
10
    if (dp[n][egg] != 0) return dp[n][egg];
11
    int min = n; // when you drop at each floor starting from 1
12
    for (int i = 1; i < n; i++) {
13
      int eggBreak = 1 + eggDrop(i - 1, egg - 1, dp); // drops needed if egg breaks at this floor
14
      int noEggBreak =
15
          1 + eggDrop(n - i, egg, dp); // drops needed if egg does not break at this floor
16
      int moves =
17
          Math.max(eggBreak, noEggBreak); // since we want certain moves for n floor take max
18
      min = Math.min(min, moves);
19
    }
20
    dp[n][egg] = min;
21
    return min;
22
  }
23
}