You are given K eggs, and you have access to a building with N floors from 1 to N. Each egg is identical in function, and if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0  F  N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break. Each move, you may take an egg if you have an unbroken one and drop it from any floor X with 1  X  N. Your goal is to know with certainty what the value of F is. What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F? Example: Input: K  1, N  2 Output: 2 Explanation: Drop the egg from floor 1.  If it breaks, we know with certainty that F  0. Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F  1. If it didn't break, then we know with certainty F  2. Hence, we needed 2 moves in the worst case to know what F is with certainty. A Dynamic Programming based Python Program for the Egg Dropping Puzzle Keyword arguments: n  number of floors k  number of eggs A 2D table where entery eggFloorij will represent minimum number of trials needed for i eggs and j floors. We need one trial for one floor and 0 trials for 0 floors We always need j trials for one egg and j floors. Fill rest of the entries in table using optimal substructure property eggFloornk holds the result
# A Dynamic Programming based Python Program for the Egg Dropping Puzzle
INT_MAX = 32767


def egg_drop(n, k):
    """
    Keyword arguments:
    n -- number of floors
    k -- number of eggs
    """
    # A 2D table where entery eggFloor[i][j] will represent minimum
    # number of trials needed for i eggs and j floors.
    egg_floor = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

    # We need one trial for one floor and 0 trials for 0 floors
    for i in range(1, n+1):
        egg_floor[i][1] = 1
        egg_floor[i][0] = 0

    # We always need j trials for one egg and j floors.
    for j in range(1, k+1):
        egg_floor[1][j] = j

    # Fill rest of the entries in table using optimal substructure
    # property
    for i in range(2, n+1):
        for j in range(2, k+1):
            egg_floor[i][j] = INT_MAX
            for x in range(1, j+1):
                res = 1 + max(egg_floor[i-1][x-1], egg_floor[i][j-x])
                if res < egg_floor[i][j]:
                    egg_floor[i][j] = res

    # eggFloor[n][k] holds the result
    return egg_floor[n][k]
