Egg drop puzzle

Find the fewest drops needed, in the worst case, to find the highest floor an egg can be dropped from without breaking.

The idea

Dropping an egg from floor x has two outcomes. It breaks: one egg fewer, and only the x-1 floors below are left to search. It survives: the same eggs remain, and only the floors above x are left. dp[k, f] tries every possible x and keeps the one with the smallest worst case.

Code

public static int EggDrop(int eggs, int floors) {
    var dp = new int[eggs + 1, floors + 1];
    for (int f = 1; f <= floors; f++) dp[1, f] = f;
    for (int k = 2; k <= eggs; k++)
        for (int f = 1; f <= floors; f++) {
            dp[k, f] = int.MaxValue;
            for (int x = 1; x <= f; x++) {
                int worst = 1 + Math.Max(dp[k - 1, x - 1], dp[k, f - x]);
                dp[k, f] = Math.Min(dp[k, f], worst);
            }
        }
    return dp[eggs, floors];
}

Tips

• With a single egg there is no choice: test every floor from the bottom, so dp[1, f] = f.
• Adding more eggs lets the search behave more like binary search, cutting the trials needed from linear to roughly square-root.

In the .NET library

This brute-force version tries every floor x, costing O(floors) per cell and O(eggs × floors²) overall. A binary search over x, or reframing the state as "trials and eggs" instead of "eggs and floors", brings it down to O(eggs × floors log floors) or better.