DP #12. Egg Dropping - mbhushan/dynpro GitHub Wiki

(12). Egg Dropping.

Given some number of floors and some number of eggs, what is the minimum 
number of attempts it will take to find out from which floor egg will break.

Formula:
i <- egg
j <- floor

if (i > j) { //eggs > floors
    T[i][j] = T[i-1][j]
} else {
    // Min ( 1 + Max(Break case, No Break case) for all k in range of [1, j] )
    T[i][j] = 1 + Min (
                      Max (T[i-1][k-1], T[i][j-k] // 1 <= k <= j;
                      );

}

public int calculate(int eggs, int floors) {
		int T[][] = new int[eggs + 1][floors + 1];
		int c = 0;
		for (int i = 0; i <= floors; i++) {
			T[1][i] = i;
		}
		for (int e = 2; e <= eggs; e++) {
			for (int f = 1; f <= floors; f++) {
				T[e][f] = Integer.MAX_VALUE;
				for (int k = 1; k <= f; k++) {
					c = 1 + Math.max(T[e - 1][k - 1], T[e][f - k]);
					if (c < T[e][f]) {
						T[e][f] = c;
					}
				}
			}
		}
		return T[eggs][floors];
	}

(egg, floor)	1	2	3	4	5	6	7
1	0	1	2	3	4	5	6
2	0	1	2	2	2	3	3

Egg Dropping

• Time Complexity: (eggs * floors * floors)
• Space Complexity: (eggs * floors)