LeetCode 1884.鸡蛋掉落-两枚鸡蛋：动态规划

【LetMeFly】1884.鸡蛋掉落-两枚鸡蛋：动态规划

力扣题目链接：https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：

输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

提示：

• 1 <= n <= 1000

解题方法：动态规划

使用dp[i]表示i层的建筑使用两枚鸡蛋最少的确定次数。初始值dp[0] = 0，其余dp[i] = ∞。

为了计算dp[i]，我们第一枚鸡蛋可以从楼层j开始尝试：

• 若鸡蛋碎了，说明答案在[1, j - 1]，并且只剩一枚鸡蛋了，必须从1楼开始尝试到j - 1楼，所需次数为1 + (j - 1) = j；
• 若鸡蛋没碎，[1, j - 1]层直接排除了，对于剩下的i - j层，方法和1到i - j层相同，所需次数为1 + (dp[i - j])。

也就是说，第一枚鸡蛋从j层开始尝试的话，所需总次数为(一定可以测出安全楼层)max(j, 1 + dp[i - j])。

所有j中，所需次数最小的那个，即为dp[i]的值。

• 时间复杂度 O ( n 2 ) O(n^2) O(n2)
• 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++

class Solution {
public:
    int twoEggDrop(int n) {
        vector<int> dp(n + 1, 100000);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = min(dp[i], max(j, dp[i - j] + 1));
            }
        }
        return dp.back();
    }
};

Go

package main

func twoEggDrop(n int) int {
    dp := make([]int, n + 1)
    for i := range(dp) {
        dp[i] = 10000
    }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] = min(dp[i], max(j, dp[i - j] + 1))
        }
    }
    return dp[n]
}

Java

import java.util.Arrays;

class Solution {
    public int twoEggDrop(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 10000);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.min(dp[i], Math.max(j, dp[i - j] + 1));
            }
        }
        return dp[n];
    }
}

Python

class Solution:
    def twoEggDrop(self, n: int) -> int:
        dp = [0] + [10000] * n
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i] = min(dp[i], max(j, dp[i - j] + 1))
        return dp[-1]

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142906976