Example: Egg Drop - rFronteddu/general_wiki GitHub Wiki

You are given floors and eggs and are asked to find the minimum number of attempts to find from which floor the egg will break.

// i is the number of eggs // j is the number of floors

-	1	2	3	4	5	6
1	1	2	3	4	5	6
2	1	2	2	3	3	3

egg(eggs, floors)
    let d[1..eggs, 1..floors] be a table

    for j = 1 tp floors
        // with 1 egg it takes as many attempts as floors in the worst case
        d[1,j] = j

    for i = 2 to eggs
        for j = 1 to floors
            if i > j
                // if the number of eggs is bigger than the number of floors, we can use previously computed solution
                d[i,j] = d[i-1, j]
            else 
                d[i,j] = max
                // we need to find the floor that optimizes the number of trials
                for k = 1 to j
                    // 1 comes from the fact that we test the current floor k
                    // if the egg breaks, we have to check if the egg breaks earlier and we are left with 1 less egg and k-1 floors -> d[i-1, k-1]
                    // if the egg doesn't break, we are left with the same number of egg and j-k floors
                    // we use max because we want the worst of the two cases
                    q = 1 + max(d[i-1, k-1],  d[i, j-k])
                    if q < d[i,j]
                        d[i,j] = q

     print("the worst case is: " d[eggs, floors])