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 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 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 eggfloor n k holds the result
INT_MAX = 32767


def egg_drop(n, k):
    
    
    
    egg_floor = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

    
    for i in range(1, n+1):
        egg_floor[i][1] = 1
        egg_floor[i][0] = 0

    
    for j in range(1, k+1):
        egg_floor[1][j] = j

    
    
    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

    
    return egg_floor[n][k]