887 Super Egg Drop

887. Super Egg Drop

1. Question

You are givenKeggs, and you have access to a building withNfloors from1toN.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floorFwith0 <= F <= Nsuch that any egg dropped at a floor higher thanFwill break, and any egg dropped at or below floorFwill not break.

Eachmove, you may take an egg (if you have an unbroken one) and drop it from any floorX(with 1 <= X <= N).

Your goal is to know with certainty what the value ofFis.

What is the minimum number of moves that you need to know with certainty whatFis, regardless of the initial value ofF?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1. 1 <= K <= 100

2. 1 <= N <= 10000

2. Implementation

(1) Memoization

(2) Memoization + Binary Search

思路:

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] cache = new int[N + 1][K + 1];

        for (int[] row : cache) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        return getMinMoves(N, K, cache);
    }

    public int getMinMoves(int floors, int eggs, int[][] cache) {
        if (floors <= 1) {
            return floors;
        }

        if (eggs <= 0) {
            return 0;
        }

        if (eggs == 1) {
            return floors;
        }

        if (cache[floors][eggs] != Integer.MAX_VALUE) {
            return cache[floors][eggs];
        }

        int start = 1, end = floors;
        int minMoves = Integer.MAX_VALUE;
        // broken is increasing with floors
        // unbroken is decreasing with floors
        // in order minimize Math.max(broken, unbroken), we use to binary search to find the smallest floor, that
        // make broken >= unbroken
        while (start <= end) {
            int mid = start + (end - start) / 2;

            int broken = getMinMoves(mid - 1, eggs - 1, cache);
            int unbroken = getMinMoves(floors - mid, eggs, cache);

            minMoves = Math.min(minMoves, 1 + Math.max(broken, unbroken));

            if (broken == unbroken) {
                break;
            }
            else if (broken < unbroken) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        cache[floors][eggs] = minMoves;
        return minMoves;
    }
}

(3) DP

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[N + 1][K + 1];
        int moves = 0;
        while (dp[moves][K] < N) {
            ++moves;
            for (int k = 1; k <= K; k++) {
                dp[moves][k] = dp[moves - 1][k - 1] + dp[moves - 1][k] + 1; 
            }
        }
        return moves;
    }
}

3. Time & Space Complexity

(1) Memoization: 时间复杂度O(K * N^2), 空间复杂度O(KN)

(2) Memoization + Binary Search: 时间复杂度O(K * N* logN), 空间复杂度O(KN)

(3) DP: 时间复杂度O(KlogN), 空间复杂度O(KN)