# 887. Super Egg Drop

鸡蛋从第p层扔才会碎，现在有K个鸡蛋和N层，每步可以选择一个楼层往下扔，问至少需要多少步能找出p, p可以是N内任意一层。问题被鸡蛋数分成了K步，每步选择一个楼层扔，受限于楼层数。因此让dp\[i]\[j]表示i个鸡蛋在j层楼至少需要的步数，从\[0, j]遍历k扔，每次扔会碎或不碎，碎说明需要剩下i-1个蛋检测之前k-1层，没碎则是再i个蛋检测楼上的j-k层，因此 dp\[i]\[j] = min(dp\[i]\[j], 1 + max(dp\[i - 1]\[k - 1] + dp\[i]\[j-k]))。

然而这并不是最优解。最优解需要把最终所求encoding进状态，而把限制当作值。让dp\[i]\[j]表示用i步和j个蛋最大能检测的层数。假设dp\[i]\[j] == n, 走出最优一步到m层并拿出一个鸡蛋往下扔，会出现两种情况:

1. 碎了: 说明目标楼层一定在\[0, m], m最大可能是用剩下的i-1步和j-1个鸡蛋能检测的最多的楼层，即dp\[i - 1]\[j-1]。
2. 没碎: 说明目标楼层在\[m + 1, n]，n最大可能是剩下的i-1步和j个鸡蛋最多能检测的层数dp\[i-1]\[j]。

```cpp
/*
 * @lc app=leetcode id=887 lang=cpp
 *
 * [887] Super Egg Drop
 *
 * https://leetcode.com/problems/super-egg-drop/description/
 *
 * algorithms
 * Hard (25.09%)
 * Likes:    461
 * Dislikes: 47
 * Total Accepted:    9.9K
 * Total Submissions: 38.4K
 * Testcase Example:  '1\n2'
 *
 * 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 <= K <= 100
 * 1 <= N <= 10000
 * 
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
        int i = 0;
        while (dp[i][K] < 0) {
            ++i;
            for (int j = 1; j <= K; ++j) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1;
            }
        }
        return i; 
    }
};
// @lc code=end
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/887.-super-egg-drop.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.