1
class Solution {
2

3
  int[][] dp;
4

5
  public int superEggDrop(int k, int n) {
6
    dp = new int[k + 1][n + 1];
7

8
    for (int i = 0; i <= k; i++) {
9
      Arrays.fill(dp[i], -1);
10
    }
11

12
    return solve(k, n);
13
  }
14

15
  public int solve(int e, int f) {
16
    if (f == 0 || f == 1) {
17
      return f;
18
    }
19

20
    if (e == 1) {
21
      return f;
22
    }
23

24
    if (dp[e][f] != -1) {
25
      return dp[e][f];
26
    }
27

28
    int high = f;
29
    int low = 1;
30
    int min = Integer.MAX_VALUE;
31

32
    while (low <= high) {
33
      int k = low + (high - low) / 2;
34

35
      int l = 0;
36
      int r = 0;
37

38
      if (dp[e - 1][k - 1] != -1) {
39
        l = dp[e - 1][k - 1];
40
      } else {
41
        l = solve(e - 1, k - 1);
42
      }
43

44
      if (dp[e][f - k] != -1) {
45
        r = dp[e][f - k];
46
      } else {
47
        r = solve(e, f - k);
48
      }
49

50
      if (l > r) {
51
        high = k - 1;
52
      } else {
53
        low = k + 1;
54
      }
55

56
      int temp = Math.max(l, r) + 1;
57
      min = Math.min(min, temp);
58
    }
59

60
    return dp[e][f] = min;
61
  }
62
}
63

64
// -------------------------TLE--------------------------
65

66
// class Solution {
67
// public int superEggDrop(int k, int n) {
68
// int [][]dp=new int[k+1][n+1];
69

70
// for(int i=1;i<=k;i++){
71
// for(int j=1;j<=n;j++){
72
// if(i==1){
73
// dp[i][j]=j;
74
// }else if(j==1){
75
// dp[i][j]=1;
76
// }else{
77
// int min=Integer.MAX_VALUE;
78

79
// for(int m=j-1,p=0;m>=0;m--,p++){
80
// int max=Math.max(dp[i][m],dp[i-1][p]);
81

82
// min=Math.min(min,max);
83
// }
84

85
// dp[i][j]=min+1;
86
// }
87
// }
88
// }
89

90
// return dp[k][n];
91
// }
92
// }