# 887.Super Egg Drop

**887.Super Egg Drop**

难度：hard

> 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。 你的目标是确切地知道 F 的值是多少。 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

```
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
```

示例 2：

```
输入：K = 2, N = 6
输出：3
```

示例 3：

```
输入：K = 3, N = 14
输出：4
```

提示：

```
 1 <= K <= 100
 1 <= N <= 10000
```

解决方法：假设K个鸡蛋，n次可以测试的最高楼层高度为H\[K]\[N]，将第一个鸡蛋放在N层去测试，则分为两种情况，如果蛋碎了，则剩下需要测试的楼层为H\[K-1]\[N-1]层；如果没碎，则剩下需要测试的楼层为H\[K]\[N-1]层。所以H\[K]\[N]=H\[K-1]\[N-1]+H\[K]\[N-1]+1。 基本代码如下：

```
class Solution {
public:
    int superEggDrop(int K, int N) {
        int cnt=0;
        vector<int> num(K+1,0);
        while(num[K]<N)
        {
            for(int i=K;i>0;i--)
                num[i]+=num[i-1]+1;
            cnt++;
        }
        return cnt;
        
    }
};
```

从最开始的0次开始，所有鸡蛋0次测试的层数都为0，所以初始化num为0.然后楼层根据递归公式逐渐增加，当最大可测试楼层大于N时，返回次数即为所求。


---

# 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://dfine.gitbook.io/leetcode/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.