Drop Eggs II (ladder)

Description

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

Link

Lintcode_ladder geeksForGeeks

Method

1. recursion, dfs, (may use memo searching)
2. dp

Example

1. 1

class Solution {
public:
    /**
     * @param m the number of eggs
     * @param n the umber of floors
     * @return the number of drops in the worst case
     */
    // ---------------------------------------------------------- 
    // Version 1
    int dropEggs2(int m, int n) {
        // Write your code here
        // if only one or no floor
        if (n == 1 || n == 0) {
            return n;
        }
        // if one egg
        if (m == 1) {
            return n;
        }
        int min = INT_MAX;
        int x;
        int res;
        for (x= 1; x <= n ; x++) {
            res = max(dropEggs2(m-1, x-1), dropEggs2(m, n-x));
            if (res < min) {
                min = res;
            }
        }
        return min + 1;
    }
    // ---------------------------------------------------------- 
    // Version 2
    int dropEggs2(int m, int n) {
        // dp for the m floors and n eggs
        vector<vector<int>> eggFloor(m + 1, vector<int>(n+1, 0));
        // dp init
        // one floor need one trial
        // 0 floor need 0 trial
        for (int i = 1; i <= m; ++i) {
            eggFloor[i][1] = 1;
            eggFloor[i][0] = 0;
        }
        // init dp
        // for one egg and other floors need floors trial
        for (int j = 1; j <= n; ++j) {
            eggFloor[1][j] = j;
        }
        // fill rest of the entry
        // i for floors
        // j for eggs
        // x for rest eggs
        for (int i = 2; i <= m; ++i) {
            for (int j = 2; j <= n; ++j) {
                eggFloor[i][j] = INT_MAX;
                for (int x = 1; x <= j; ++x ) {
                    // tracking the intermediate result
                    // we perform 1 trial + rest possible trial
                    // eggFloor[i-1][x-1] : i-1 floor, x - 1 eggs
                    // eggFloor[i][j-x] : i floor, j-x eggs
                    int res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                    if (res < eggFloor[i][j]) {
                        eggFloor[i][j] = res;
                    }
                }
            }
        }
        return eggFloor[m][n];
    }
};

Similar problems

x

Tags

x