二维dp，LeetCode 887. 鸡蛋掉落

一、题目

1、题目描述

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

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

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

2、接口描述

python3

 ​

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:

cpp

 ​

class Solution {
public:
    int superEggDrop(int k, int n) {

    }
};

C#

 ​

public class Solution {
    public int SuperEggDrop(int k, int n) {

    }
}

3、原题链接

887. 鸡蛋掉落

二、解题报告

1、思路分析

我们换一个角度思考问题，假如已知操作次数i，在拥有 j 枚鸡蛋的情况下，我们能够测出的最大楼层是多少？

定义状态 f(i, j) 为 拥有 j  枚鸡蛋可扔 i 次能够测的最大楼层高度

那么 我们可以扔一枚鸡蛋到 f(i - 1, j - 1) + 1层：

鸡蛋碎了，那么 只需在 [1, f(i - 1, j - 1)] 中扔鸡蛋，就能确定 楼层数

鸡蛋没碎，那么问题变成了 有 i - 1次机会，j 枚鸡蛋能够测得的最大楼层数，注意因为没碎，所以我们的最大楼层数就是 f(i - 1, j - 1) + 1 + f(i - 1, j)

 具体实现时可以优化掉第一维

2、复杂度

时间复杂度： O(nk)空间复杂度：O(k)

3、代码详解

python3

 ​

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        f = [0] * (k + 1)
        for i in count(1):
            for j in range(k, 0, -1):
                f[j] += f[j - 1] + 1
                if f[j] >= n:
                    return i

cpp

 ​

class Solution {
public:
    int superEggDrop(int k, int n) {
        std::vector<int> f(k + 1);
        for (int i = 1; ; ++ i) {
            for (int j = k; j; -- j) {
                f[j] += f[j - 1] + 1;
                if (f[j] >= n) {
                    return i;
                }
            }
        }
    }
};

C#

 ​

public class Solution {
    public int SuperEggDrop(int k, int n) {
        int[] f = new int[k + 1];
        for (int i = 1; ; ++ i) {
            for (int j = k; j > 0; -- j) {
                f[j] += f[j - 1] + 1;
                if (f[j] >= n) {
                    return i;
                }
            }
        }
    }
}