State
dp[k][n] = min trials with k eggs, n floors.
Advertisement
Transition
Drop from floor x. If breaks: k-1 eggs, x-1 floors below. If not: k eggs, n-x floors above. Worst case + 1.
dp[k][n] = min over x in [1,n] of
1 + max(dp[k-1][x-1], dp[k][n-x]);Advertisement
Complexity
Naive O(K × N²). Binary search optimization → O(K × N × log N). Direct formula version O(K × N).
Formula version
// dp[k][m] = max floors testable with k eggs, m moves
// dp[k][m] = 1 + dp[k-1][m-1] + dp[k][m-1]
// Find smallest m such that dp[K][m] >= N