gistfile1.java

public class VaseDrop {

    private static int[][] matrix;

    public static void main(String[] args) {
        int k = 100;
        int v = 2;
        matrix = new int[k + 1][v + 1];
        for (int[] row : matrix)
            for (int i = 0; i < row.length; i++)
                row[i] = -1;

        int solution = drops(k, v);
        System.out.println(solution);
    }

    // k = # floors to test
    // v = # vases to test with
    public static int drops(int k, int v) {
        // if this "problem" has been solved
        // before, get stored solution
        if (matrix[k][v] != -1)
            return matrix[k][v];

        // `v == 1` -> if only one vase can
        // be used, all k floors must be checked.
        if (v == 1)
            return matrix[k][v] = k;

        if (k == 0)
            return matrix[k][v] = 0;

        // `bestCase` is essentially the
        // minumum number of drops needed,
        // because we want the best algorithm
        int bestCase = Integer.MAX_VALUE;
        
        for (int i = 1; i <= k; i++) {
            // `worstCase` is the maximum of
            // the two scenarios that could occur:
            // 1) the vase breaks. We need to test all
            //    floors beneath i (i - 1), and we have
            //    one less vase to use (v - 1)
            // 2) the vase doesn't break. We need to test
            //    all floors between i and k (k - i),
            //    and we can reuse the last vase (k
            //    stays the same
            //
            // 1 is added because we just used a drop
            int worstCase = 1 + max(
                    drops(i - 1, v - 1),
                    drops(k - i, v)
            );

            // We want the lowest of all worstCases,
            // which will be the bestCase
            if (worstCase < bestCase)
                bestCase = worstCase;
        }

        // store solution and return it
        return matrix[k][v] = bestCase;
    }

    // get max of two integers
    private static int max(int a, int b) {
        return a > b ? a : b;
    }
}