Add Eggdroping puzzle

dpacmen · web-flow · commit a92743cd6f3e · 2017-10-05T19:26:35.000+05:30
Dynamic Programming solution for the popular Egg Dropping Puzzle
diff --git a/Dynamic Programming/EggDropping.java b/Dynamic Programming/EggDropping.java
@@ -0,0 +1,54 @@
+//Dynamic Programming solution for the Egg Dropping Puzzle
+public class EggDropping
+{
+	
+	// min trials with n eggs and m floors 
+	
+	private static int minTrials(int n, int m)
+	{
+	    
+		int eggFloor[][] = new int[n+1][m+1];
+		int result, x;
+		
+		for (int i = 1; i <= n; i++)
+		{
+		    eggFloor[i][0] = 0;   // Zero trial for zero floor.
+			  eggFloor[i][1] = 1;   // One trial for one floor 
+		}
+		
+	  // j trials for only 1 egg
+		
+    for (int j = 1; j <= m; j++)
+			 eggFloor[1][j] = j;
+		
+		// Using bottom-up approach in DP
+		
+    for (int i = 2; i <= n; i++)
+		{
+			for (int j = 2; j <= m; j++)
+			{
+				eggFloor[i][j] = Integer.MAX_VALUE;
+				for (x = 1; x <= j; x++)
+				{
+					result = 1 + Math.max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
+          
+					//choose min of all values for particular x
+          if (result < eggFloor[i][j])
+						eggFloor[i][j] = result;
+				}
+			}
+		}
+		return eggFloor[n][m];
+
+	}
+		
+	//testing program
+	public static void main(String args[])
+	{
+		int n = 2, m = 4;
+    //result outputs min no. of trials in worst case for n eggs and m floors
+    
+    int result = minTrials(n, m);
+		System.out.println(result); 
+	}
+}
