Skip to content

887. Super Egg Drop

887. Super Egg Drop

题目: https://leetcode.com/problems/super-egg-drop

难度: Hard

题意：

  1. 已知蛋从F楼丢下会坏
  2. 现在给你K个蛋，在N层楼中，请问最坏情况最少要试验几次才能知道F的精确值
  3. 如果蛋丢下来不会坏，那么可以捡起来继续丢

思路：

  • 又是一个脑筋急转弯的题目，我们来看看K=1的情况。由于只有一个蛋，坏了就没了，所以只能一层一层往下丢。一层丢下，蛋坏了，说明F=1，反之，继续去二层丢，所以K=1时，最坏情况要试验N次
  • 当K>=2时，由于蛋有多余，可以大胆的去中间丢，这样就可以少丢几次
  • 因此，令cache[K][N]表示K个蛋在N层试验最少要试验的次数，假设第一次要在i层丢蛋，那么分成了两个子问题，如果蛋没碎了，那么最少次数等于cache[k][N-i]+1，如果蛋碎了，那么最少次数等于cache[k-1][i-1]+1
  • 那么这个题就变成了cache[k][N] = min[1<=i<=N]{max{cache[k][N-i], cache[k - 1][i - 1] + 1} + 1}，时间复杂度是o(kNN)
  • 但是看数据范围，k<=100，N<=10000，o(kNN)肯定是过不了的
  • 注意到，cache[k][N]是非严格递增输了，且递增值不会超过1，即0<=cache[k][i+1]-cache[k][i]<=1
  • 计算过程中令cache[k][N]最优解的i，跟cache[k][N+1]最优解的j，关系是0<=j-i<=1
  • 因此在处理的过程，固定k，递推N，保存上一个最优解i，继续推出下一个最优解

代码：

class Solution {
    private static int[][] cache;

    private static void init() {
        if (cache == null) {
            cache = new int[101][10001];

            for (int i = 1;i <= 10000;i++) {
                cache[1][i] = i;
            }

            for (int i = 2;i <= 100;i++) {
                cache[i][1] = 0;
                cache[i][1] = 1;
                cache[i][2] = 2;

                int idx = 1;
                for (int j = 3;j <= 10000;j++) {

                    while (cache[i - 1][idx + 1] <= cache[i][j - idx - 2]) {
                        idx++;
                    }

                    cache[i][j] = Math.max(cache[i - 1][idx], cache[i][j - idx - 1]) + 1;
                }
            }
        }
    }

    public int superEggDrop(int K, int N) {
        init();
        return cache[K][N];
    }
}
回到顶部