EggDropping.java

public class EggDropping {
    static int findFloor(int n, int k) {
        // n: number of eggs
        // k: number of floors
        int[][] memo = new int[n + 1][k + 1];
        // initialize
        // 0 trial for 0th floor
        // 1 trial for 1st floor
        for (int i = 1; i <= n; i++) {
            memo[i][0] = 0;
            memo[i][1] = 1;
        }
        // in case of only one egg is given
        for (int i = 1; i <= k; i++) {
            memo[1][i] = i;
        }

        // fill the rest
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                int minimum = Integer.MAX_VALUE;
                for (int x = 1; x <= j; x++) {
                    int temp = 1 + Math.max(memo[i - 1][x - 1], memo[i][j - x]);
                    minimum = Math.min(minimum, temp);
                }
                memo[i][j] = minimum;
            }
        }
        return memo[n][k];
    }

    public static void main(String[] args) {
        int n, k;
        n = 2;
        k = 36;
        System.out.println(findFloor(n, k));
    }
}