超级蛋掉落-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
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，继续推出下一个最优解

代码：

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

该分类下的相关小册推荐：

编程之道-算法面试(上)

业务开发实用算法精讲

数据结构与算法之美

数据结构与算法(上)

编程之道-算法面试(下)

算法面试通关 50 讲

数据结构与算法(下)