The trick here is to name the state correctly, then let the implementation follow. For 887. Super Egg Drop, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming, binary search, two pointers.
The notes already sitting in the source point us in the right direction:
- DP
- TLE
- 64 / 121 test cases passed.
- time: O(KN^2), space: O(KN)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are superEggDrop, dfs, comb, f_slow, f.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(KNlogN), space: O(KN)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//TLE
03//64 / 121 test cases passed.
04//time: O(KN^2), space: O(KN)
05class Solution {
06public:
07 int superEggDrop(int K, int N) {
08 vector<vector<int>> dp(K+1, vector(N+1, INT_MAX));
09
10 for(int k = 1; k <= K; k++){
11 for(int n = 0; n <= N; n++){
12 if(k == 1){
13 dp[k][n] = n;
14 continue;
15 }
16
17 if(n == 0){
18 dp[k][n] = 0;
19 continue;
20 }
21
22 for(int i = 1; i <= n; i++){
23 dp[k][n] = min(dp[k][n],
24 /*egg breaks at ith floor,
25 remain k-1 eggs,
26 and i-1 floors to try
27 */
28 max(dp[k-1][i-1],
29 /*
30 egg does not break,
31 remain k eggs,
32 and n-i floors to try
33 */
34 dp[k][n-i]
35 //drop once
36 )+1);
37 // cout << "i: " << i << ", choose: " << "dp[" << k-1 << "][" << i-1 << "]: " << dp[k-1][i-1] << ", and dp[" << k << "][" << n-i << "]: " << dp[k][n-i] << endl;
38 }
39 // cout << "(" << k << ", " << n << "): " << dp[k][n] << endl;
40 }
41 }
42
43 return dp[K][N];
44 }
45};
46
47//recursion DP + binary search to speed up
48//https://github.com/keineahnung2345/fucking-algorithm/blob/note/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E9%AB%98%E6%A5%BC%E6%89%94%E9%B8%A1%E8%9B%8B%E9%97%AE%E9%A2%98.md
49//Runtime: 144 ms, faster than 26.59% of C++ online submissions for Super Egg Drop.
50//Memory Usage: 29.5 MB, less than 14.29% of C++ online submissions for Super Egg Drop.
51//time: O(KNlogN), space: O(KN)
52class Solution {
53public:
54 vector<vector<int>> dp;
55
56 int dfs(int K, int N){
57 if(dp[K][N] != INT_MAX){
58 return dp[K][N];
59 }
60
61 if(K == 1){
62 dp[K][N] = N;
63 return dp[K][N];
64 }
65
66 if(N == 0){
67 dp[K][N] = 0;
68 return dp[K][N];
69 }
70
71 int l = 1, r = N;
72
73 /*
74 think of dfs(K-1, mid-1) as a function of mid,
75 and it increases with mid
76 think of dfs(K, N-mid) as a function of mid,
77 and it decreases with mid
78 we want to find where they intersect
79 i.e. use binary search to find "valley"
80 */
81 while(l <= r){
82 int mid = l + (r-l)/2;
83 /*
84 note that we need to use such recursive way,
85 because we won't visit "dp" in order
86 */
87 int broken = dfs(K-1, mid-1);
88 int not_broken = dfs(K, N-mid);
89 if(broken > not_broken){
90 /*
91 broken > not_broken means mid is too large,
92 (broken is an increasing function of mid,
93 not_broken is an decreasing function of mid)
94 so go left
95 */
96 r = mid-1;
97 dp[K][N] = min(dp[K][N], broken+1);
98 }else{
99 /*
100 not_broken > broken means mid is too small,
101 so go right
102 */
103 l = mid+1;
104 dp[K][N] = min(dp[K][N], not_broken+1);
105 }
106 }
107
108 return dp[K][N];
109 }
110
111 int superEggDrop(int K, int N) {
112 dp = vector<vector<int>>(K+1, vector(N+1, INT_MAX));
113 return dfs(K, N);
114 }
115};
116
117//DP, different definition
118//https://github.com/keineahnung2345/fucking-algorithm/blob/note/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E9%AB%98%E6%A5%BC%E6%89%94%E9%B8%A1%E8%9B%8B%E8%BF%9B%E9%98%B6.md
119//time: O(KN), space: O(KN)
120//Runtime: 12 ms, faster than 61.24% of C++ online submissions for Super Egg Drop.
121//Memory Usage: 29.7 MB, less than 14.29% of C++ online submissions for Super Egg Drop.
122class Solution {
123public:
124 int superEggDrop(int K, int N) {
125 /*
126 dp[k][m]: how many floor we can test if we have k eggs and can throw m times
127 for k = 0(no eggs to throw) or m = 0(no chances to throw) dp[k][m] should be 0
128 */
129 vector<vector<int>> dp(K+1, vector(N+1, 0));
130 int m = 0;
131
132 //keep increasing m until dp[k][m] can test n floors
133 while(dp[K][m] < N){
134 m++;
135 for(int k = 1; k <= K; k++){
136 /*
137 we throw an egg at current floor,
138 if the egg does not break, we then go up,
139 we still have k eggs and m-1 times to throw eggs
140 dp[k][m-1]: how many floors higher than current floor
141
142 1: current floor
143
144 if the egg breaks, we then go down,
145 we still have k-1 eggs and m-1 times to throw eggs
146 dp[k-1][m-1]: how many floors lower than current floor
147 */
148 dp[k][m] = dp[k][m-1] + 1 + dp[k-1][m-1];
149 }
150 }
151 return m;
152 }
153};
154
155//Approach 3: Mathematical
156//time: O(KlogN), space: O(1)
157//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Super Egg Drop.
158//Memory Usage: 5.9 MB, less than 100.00% of C++ online submissions for Super Egg Drop.
159class Solution {
160public:
161 int comb(int K, int N){
162 /*
163 N!/((N-K)! * K!)
164 = N * (N-1) * (N-2) * ... * (N-(K-1)) / K!
165 */
166
167 int res = 1;
168
169 for(int i = 1; i <= K; i++){
170 res *= i * (N-(i-1));
171 }
172
173 return res;
174 }
175
176 /*
177 f(T, K) -> N
178 T: #moves, K: #eggs, N: #floors we can test
179
180 // ... = egg breaks + current try + egg not break
181 f(T, K) = f(T-1, K-1) + 1 + f(T-1, K)
182
183 now define g(T, K) = f(T, K) - f(T, K-1)
184 g(T, K) = [f(T-1, K-1)-f(T-1, K-2)] + [f(T-1, K)-f(T-1, K-1)]
185 = g(T-1, K-1) + g(T-1, K)
186
187 they are just binomial coefficient!
188 (https://en.wikipedia.org/wiki/Binomial_coefficient)
189 so g(T, K) = comb(T, K)
190
191 now we can write f(T, K)
192 = [f(T, K) - f(T, K-1)] + [f(T, K-1) - f(T, K-2)] + ... + [f(T,2)-f(T,1)] + f(T,1)
193 = g(T, K) + g(T, K-1) + ... g(T, 2) + f(T, 1)
194 because f(T, 1) = 1(only one eggs to try),
195 and g(T, 1) = comb(T, 1) = T = f(T, 1)
196 so f(T, K) = g(T, K) + g(T, K-1) + ... g(T, 2) + g(T, 1)
197 = sigma(x = 1 to K) g(T, x)
198 = sigma(x = 1 to K) comb(T, x)
199 */
200 int f_slow(int T, int K, int N){
201 //T: #moves
202 int res = 0;
203 for(int x = 1; x <= K; x++){
204 res += comb(K, N);
205 if(res >= N) break;
206 }
207 return res;
208 }
209
210 //efficient version
211 int f(int T, int K, int N){
212 //T: #moves
213 int comb_N_x = 1;
214 int res = 0;
215 /*
216 comb_N_1: T/1 = T
217 comb_N_2: T*(T-1)/2
218 comb_N_3: T*(T-1)*(T-2)/(2*3)
219 ...
220 comb_N_K: T*(T-1)*(T-2)*...*(T-K)/K!
221 */
222 for(int x = 1; x <= K; x++){
223 comb_N_x *= (T-(x-1));
224 comb_N_x /= x;
225 res += comb_N_x;
226 if(res >= N) break;
227 }
228 return res;
229 }
230
231 int superEggDrop(int K, int N) {
232 /*
233 moves taken to decide what F is,
234 it's in the range [1,N]
235
236 note that when K=1 and N=1,
237 we need to take 1 move to decide what F is
238 */
239 int lo = 1, hi = N;
240
241 //binary search to find a mid s.t. f(mid, K, N)
242 while(lo <= hi){
243 int mid = (lo+hi)/2;
244
245 int tmp;
246 if((tmp = f(mid, K, N)) == N){
247 return mid;
248 }else if(tmp < N){
249 lo = mid+1;
250 }else if(tmp > N){
251 hi = mid-1;
252 }
253 }
254
255 return lo;
256 }
257};Cost
Complexity
Time
O(KNlogN), space: O(KN)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.