Drop Eggs II

There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.

You're given m eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.

Example:

Given m = 2, n = 100 return 14

Given m = 2, n = 36 return 8

Code:

public class Solution {
    /**
     * @param m the number of eggs
     * @param n the umber of floors
     * @return the number of drops in the worst case
     */
    public int dropEggs2(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        //state: f[x][y] represents the minimum number of trials that needed for verifying the worst case of y floors with x eggs
        int[][] f = new int[m + 1][n + 1];

        //initialization:
        //when there is only one egg
        for (int i = 1; i <= n; i++) {
            f[1][i] = i;
        }
        //when there is only one floor
        for (int i = 1; i <= m; i++) {
            f[i][1] = 1;
        }

        //function:
        /* drop one egg (out of m) on any arbitrary floor k (out of n), there will be two cases:
        * (1). egg - break, number of trials is reduced to subproblem(m - 1, k - 1)
        * (2). egg - !break, number of trails is reduced to subproblem(m, n -k)
        * The worst case amoung these two will be the total trials required after floor x
        */
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                f[i][j] = Integer.MAX_VALUE;
                for (int k = 1; k < j; k++) {
                    int worstCase = Math.max(f[i - 1][k - 1], f[i][j - k]) + 1; // add one for current drop
                    f[i][j] = Math.min(f[i][j], worstCase); //find the minimum amoung these decisions
                }
            }
        }

        //answer:
        return f[m][n];
    }
}

results matching ""

    No results matching ""