887. Super Egg Drop

You are given K eggs, and you have access to a building with N floors from 1 to N.

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

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

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

Your goal is to know with certainty what the value of F is.

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

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

第一種方法是暴力解的Dynamic programming，因為這個方法會確認所有可能的情形。 dp[n][k]代表最少的moves去用k個蛋檢查n層。 在第i層把蛋丟下去： 1. 破掉: 用 (k - 1) 個蛋往下測 (i - 1) 層 2. 沒破: 用 k 個蛋往上測 (n - i) 層 最糟的情形是 max(dp[i - 1][k - 1], dp[n - i][k]) + 1，所以dp[n][k]可以從下面這個關係求得： dp[n][k] = min{max( dp[i - 1][k - 1], dp[n - i][k] ) + 1}, 1 <= i <= N 但這個暴力解無法通過Leetcode的OJ。

// Dynamic Programming (Brute Force)
int superEggDrop(int K, int N) { // time: O(K * N^2); space: O(K * N)
    // dp[n][k] is the minimum moves to check n floors with k eggs
    vector<vector<int> > dp(N + 1, vector<int> (K + 1, 0));
    for (int i = 1; i <= N; ++i) dp[i][1] = i;
    for (int j = 2; j <= K; ++j) {
        for (int i = 1; i <= N; ++i) {
            dp[i][j] = i;
            for (int k = 1; k < i; ++k) {
                dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
            } 
        }
    }
    return dp[N][K];
}

// Dynamic Programming Optimized with Binary Search
int superEggDrop(int K, int N) { // time: O(K * N * logN); space: O(K * N)
    // dp[n][k] is the minimum moves to check n floors with k eggs
    vector<vector<int> > dp(N + 1, vector<int> (K + 1, 0));
    for (int i = 1; i <= N; ++i) dp[i][1] = i;
    for (int j = 2; j <= K; ++j) {
        for (int i = 1; i <= N; ++i) {
            dp[i][j] = i;
            // dp[k - 1][j - 1] increases and dp[i - k][j] decreases as k increases
            // Binary Search
            int left = 1, right = i;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid - 1][j - 1] < dp[i - mid][j]) left = mid + 1;
                else right = mid;
            }
            dp[i][j] = min(dp[i][j], max(dp[right - 1][j - 1], dp[i - right][j]) + 1);
        }
    }
    return dp[N][K];
}

// Dynamic Programming with Optimization
int superEggDrop(int K, int N) { // time: O(K * N); space: O(K * N)
    // dp[n][k] is the minimum moves to check n floors with k eggs
    vector<vector<int> > dp(N + 1, vector<int> (K + 1, 0));
    for (int i = 1; i <= N; ++i) dp[i][1] = i;
    for (int j = 2; j <= K; ++j) {
        // Given a fixed # of eggs, dp[i - k][j] increases monotonously as i increases
        int k = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i][j] = i;
            while (k < i && dp[k - 1][j - 1] < dp[i - k][j]) ++k;
            dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
        }
    }
    return dp[N][K];
}

換個方式思考，如果dp[M][K]代表用K個蛋還有M個moves最大能檢查的樓層數量。 DP state transition: dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1 其中dp[m - 1][k - 1]代表broken case，dp[m - 1][k]代表unbroken case，1代表當前這層。 dp[M][K]類似所有可能組合的數量，和N的關係是指數成長。

// Runtime-Optimized Dynamic Programming
int superEggDrop(int K, int N) { // time: O(K * logN); space: O(K * N)
    // dp[m][k] is the maximum number of floors we can check given k eggs and m moves
    vector<vector<int> > dp(N + 1, vector<int>(K + 1, 0));
    int m = 0;
    while (dp[m][K] < N) {
        ++m;
        for (int k = 1; k <= K; ++k) {
            dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1;
        }
    }
    return m;
}

優化空間使用至O(K)。

// Space-Optimized Dynamic Programming
int superEggDrop(int K, int N) { // time: O(K * logN); space: O(K)
    vector<int> dp(K + 1, 0);
    int m = 0;
    for (; dp[K] < N; ++m) {
        for (int k = K; k >= 1; --k) {
            dp[k] += dp[k - 1] + 1;
        }
    }
    return m;
}