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];
    }
}


回到顶部