leetcode：887. 鸡蛋掉落

题目

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 **f** 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例：

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

输入：k = 2, n = 6
输出：3

输入：k = 3, n = 14
输出：4

解答 & 代码

动态规划：

动态规划数组 **dp**：dp[i][m] 代表有 k 枚鸡蛋，可以尝试扔 m 次，可以确定的 f 的最大值（即可以确定 n 层高的楼的 f，因为 0<=f<=n）

题目转换：而题目是有 k 枚鸡蛋，n 层楼，求确定 f 确切的值的最小操作次数，也就是要求当 **dp[k][m] >= n** 的最小的 **m**

⽆论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
⽆论你上楼还是下楼， 总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）

状态转移方程：dp[i][m] = dp[i][m - 1] + 1 + dp[i - 1][m - 1]
- dp[i][m - 1] 代表楼上的层数。即鸡蛋没碎，上楼继续测
- 1 ：当前楼层
- dp[i - 1][m - 1] 代表楼下的层数。即鸡蛋碎了，鸡蛋数 - 1，下楼继续测
初始化：
- dp[0][m] = 0，即如果只有 0 枚鸡蛋，那么只能确定 0 层
- dp[i][0] = 0，即如果只能仍 0 次，那么只能确定 0 层

class Solution {
public:
    int superEggDrop(int k, int n) {
        /* 动态规划数组 dp：dp[i][m] 代表有 k 枚鸡蛋，可以尝试扔 m 次，
           可以确定的 f 的最大值（即可以确定 n 层高的楼的 f，因为 0<=f<=n）*/
        // m 这一维长度设为 n，因为 m 最多不会超过 n 次（即从下往上线性扫描）
        vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));

        // 注意外循环遍历 m，否则会溢出，要用 unsigned long long
        // 求 dp[k][m] >= n 的最小的 m
        for(int m = 1; m <= n; ++m)
        {
            for(int i = 1; i <= k; ++i)
                dp[i][m] = dp[i][m - 1] + 1 + dp[i - 1][m - 1];
            if(dp[k][m] >= n)
                return m;
        }
        return -1;
    }
};

复杂度分析：

时间复杂度 O(kn)：
空间复杂度 O(kn)：

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：28.8 MB, 在所有 C++ 提交中击败了 41.37% 的用户

hot 100

[困难] 887. 鸡蛋掉落

题目

解答 & 代码