Time: O(n*k*logn), Space: O(n*k)
| 4 | public: |
| 5 | //Time: O(n*k*logn), Space: O(n*k) |
| 6 | int helper(int k, int n, vector<vector<int>>& memo){ |
| 7 | if(n == 0 || n == 1) return n; |
| 8 | if(k == 1) return n; |
| 9 | |
| 10 | if(memo[k][n] != -1) return memo[k][n]; |
| 11 | |
| 12 | int mn = INT_MAX, low = 0, high = n, temp = 0; |
| 13 | |
| 14 | while(low<=high){ |
| 15 | |
| 16 | int mid = (low + high)/2; |
| 17 | |
| 18 | /*representing both the choices with memo |
| 19 | First one, if the egg will break, no. of eggs will decreased and we have to |
| 20 | down from that floor. |
| 21 | Second one, if the egg will not break, no. of eggs will not decreased and we |
| 22 | have to go above form that floor.*/ |
| 23 | |
| 24 | int left = helper(k-1, mid-1, memo); |
| 25 | int right = helper(k, n-mid, memo); |
| 26 | |
| 27 | temp = 1 + max(left, right); |
| 28 | |
| 29 | //since we need more temp value in worst case, so need to go above |
| 30 | if(left < right) |
| 31 | low = mid+1; |
| 32 | else |
| 33 | high = mid-1; //move to the downward |
| 34 | |
| 35 | mn = min(mn, temp); //minimum number of attempts |
| 36 | } |
| 37 | return memo[k][n] = mn; |
| 38 | } |
| 39 | |
| 40 | int superEggDrop(int k, int n) { |
| 41 | //k means number of eggs, n means number of floors |