-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEggDropping.java
More file actions
69 lines (59 loc) · 1.8 KB
/
EggDropping.java
File metadata and controls
69 lines (59 loc) · 1.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package algorithm.DynamicProgramming;
/**
* The type Egg dropping.
*/
class EggDropping {
/**
* Eggdrop helper int.
*
* @param dp the dp
* @param eggs the eggs
* @param floors the floors
* @return the int
*/
public static int eggdropHelper(int[][] dp, int eggs, int floors) {
if (eggs <= 0)
return 0;
// If there are no floors, then no trials needed. OR if there is
// one floor, one trial needed.
if (floors == 1 || floors == 0)
return floors;
// We need k trials for one egg and k floors
if (eggs == 1)
return floors;
int min = Integer.MAX_VALUE;
int x, res;
// Consider all droppings from 1st floor to kth floor and
// return the minimum of these values plus 1.
if (dp[eggs][floors] == 0) {
for (x = 1; x <= floors; x++) {
res = Math.max(eggdropHelper(dp, eggs - 1, x - 1), eggdropHelper(dp, eggs, floors - x));
if (res < min)
min = res;
}
dp[eggs][floors] = min + 1;
}
return dp[eggs][floors];
}
/**
* Egg drop int.
*
* @param eggs the eggs
* @param floors the floors
* @return the int
*/
public static int eggDrop(int eggs, int floors) {
// If there are no eggs, then there can't be any tries
int[][] dp = new int[eggs + 1][floors + 1];
return eggdropHelper(dp, eggs, floors);
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]) {
int eggs = 2, floors = 10;
System.out.println("With " + eggs + " eggs and " + floors + " floors, the minimum number of trials in worst are: " + eggDrop(eggs, floors));
}
};