# 1884. Egg Drop With 2 Eggs and N Floors    • Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class Solution { public: int twoEggDrop(int n) { return superEggDrop(2, n); } private: vector> dp; int superEggDrop(int k, int N) { // dp[k][n] := the minimum number of moves to know F with k eggs and n // floors dp.resize(k + 1, vector(N + 1, -1)); return drop(k, N); } int drop(int k, int n) { if (k == 0) // no eggs -> done return 0; if (k == 1) // one egg -> drop from 1-th floor to n-th floor return n; if (n == 0) // no floor -> done return 0; if (n == 1) // one floor -> drop from that floor return 1; if (dp[k][n] != -1) return dp[k][n]; // broken[i] := drop(k - 1, i - 1) is increasing with i // unbroken[i] := drop(k, n - i) is decreasing with i // dp[k][n] := 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n // Find the first index i s.t broken[i] >= unbroken[i], // which minimizes max(broken[i], unbroken[i]) int l = 1; int r = n + 1; while (l < r) { const int m = (l + r) / 2; const int broken = drop(k - 1, m - 1); const int unbroken = drop(k, n - m); if (broken >= unbroken) r = m; else l = m + 1; } return dp[k][n] = 1 + drop(k - 1, l - 1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public int twoEggDrop(int n) { return superEggDrop(2, n); } private int[][] dp; private int superEggDrop(int k, int N) { // dp[k][n] := the minimum number of moves to know F with k eggs and n floors dp = new int[k + 1][N + 1]; Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1)); return drop(k, N); } private int drop(int k, int n) { if (k == 0) // no eggs -> done return 0; if (k == 1) // one egg -> drop from 1-th floor to n-th floor return n; if (n == 0) // no floor -> done return 0; if (n == 1) // one floor -> drop from that floor return 1; if (dp[k][n] != -1) return dp[k][n]; // broken[i] := drop(k - 1, i - 1) is increasing with i // unbroken[i] := drop(k, n - i) is decreasing with i // dp[k][n] := 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n // Find the first index i s.t broken[i] >= unbroken[i], // which minimizes max(broken[i], unbroken[i]) int l = 1; int r = n + 1; while (l < r) { final int m = (l + r) / 2; final int broken = drop(k - 1, m - 1); final int unbroken = drop(k, n - m); if (broken >= unbroken) r = m; else l = m + 1; } return dp[k][n] = 1 + drop(k - 1, l - 1); } }