Drop Eggs DP Solution


  • 3

    Here are the problem Def.

    There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case.

    Let us check the DP solution , Thanks to @zhouyangnk

    • sub-problem def.

      dp[n][m] : the minimal max drops we need if we have n-floor building and m eggs.

    • base case def.

      dp[0][m] = 0 (m >= 1)

      dp[n][1] = n (n >= 1)

      dp[n][m] = min { max { dp[i-1][m-1], dp[n-i][m] } } + 1 ( n >= i >= 1 )

    Solution

    int ans[500][500];
    int f(int n, int m){
    	if (ans[n][m] != -1) return ans[n][m];
    	if (n == 0) { ans[n][m] = 0; return 0; }
    	if (m == 1) { ans[n][m] = n; return n; }
    	int res = INT_MAX;
    	for (int i = 1; i <= n; ++i){
    		int x = max(f(i-1,m-1),f(n-i,m))+1;
    		res = min(res, x);
    	}
    	ans[n][m] = res;
    	return res;
    }
    
    int main()
    {
    	for (int i = 0; i < 500; ++i){
    		for (int j = 0; j < 500; ++j){
    			ans[i][j] = -1;
    		}
    	}
    	cout << f(39, 2) << endl;
    	return 0;
    }
    

  • 1

    I don't understand your solution. According to the problem statement you have two eggs. Once you break those you eggs you can't keep trying. And the problem is to find N, that could be any number between 1 and 100.

    You have three basic algorithms to find N with two eggs:

    • Start in the first floor and continue trying until the egg is broken. N is the previous floor. On average you will need to check N/2 floors but according to the problem statement you want to minimize the worst case, a minimax. The worst case for this approach is N (N is the last floor)
    • Use binary search. Binary search would be the best option if we have 6 eggs (log2(N)) but we only have two. In that case, the solution would be to use binary search until the egg breaks. Then start from highest position you visited where the egg didn't break and apply solution 1: linear search. In this case the worst situation will be N = 49. The first drop will be 50 and you will start a linear search from the beginning. Worst case N/2 steps (50).
    • Split the search interval in sqrt(N) slots. Check each slot until an egg breaks and start a linear search in the previous slot. The worst case is N=100 but the cost is only 2*sqrt(N) (20).

  • 0
    F

    @pbg said in Drop Eggs DP Solution:

    problem statement you have two eggs. Once you break those you eggs you can't keep trying. And the problem is to find N, that could be any n

    You are right, but in fact you do not understand the problem. We are asked to find the smallest worst number. So your 3 situations are just only possible solutions but not the result we want


  • 0
    C

  • 0
    P

    This problem has a simple O(1) solution:
    n*(n+1)/2 = floor. solve for n
    If floor = 100, n = 14

    PS: Account for the rounding of the inequality solution


  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.