楼层扔鸡蛋问题
in 个人博客 on Algorithm
刷题期间看到一道很经典的面试题，楼层扔鸡蛋，这里记录一下解题的思路。
题目意思就是，给你K个鸡蛋和N层楼，让你设计一个算法，找到第F层楼（高于这层楼扔鸡蛋，鸡蛋会破，不高于则不会破），求直到确切F的最小次数。没破的鸡蛋可以重复使用。
暴力解法
从题目的意思来看，当选中一层楼扔下去之后，要考虑两种情况：
- 鸡蛋没破，意味着F大于等于当前楼层，此时还有K个鸡蛋，需要继续向上搜索
- 鸡蛋破了，意味着F小于当前楼层，此时还有K-1个鸡蛋，需要继续向下搜索
这么一看，需要确定每一次扔鸡蛋的楼层，暴力遍历：
import java.util.Scanner;
public class Solution{
public int superEggDrop(int K, int N) {
if (N < 3 || K == 1) return N;
int min = Integer.MAX_VALUE;
for (int p = 1; p < N; p++){
min = Math.min(min, Math.max(superEggDrop(K-1,p), superEggDrop(K, N-p-1)));
}
return min + 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
int n = in.nextInt();
Solution solution = new Solution();
System.out.println(solution.superEggDrop(k,n));
}
}
这个时间复杂度太高了，每一轮递归需要遍历N，有K层递归…
动态规划
上面可以看到，影响F的是(N, K)这两个状态，同样的(N, K)被多次计算，那先算好存下来应该会好一点。
定义dp(n,k)为在这个状态下的实验的次数，
\(dp(n,k) = \min _{x \in[1, n]} \left(\max \left(dp(x-1,k-1),dp(n-x,k)\right) +1 \right)\)
状态转移写好了，那就简单了：
public class Solution{
public int superEggDrop(int K, int N) {
int d[][] = new int[K+1][N+1];
for (int i = 0;i<=K;i++){
Arrays.fill(d[i], Integer.MAX_VALUE);
}
for (int i = 0;i<=N;i++){
d[0][i] = 0;
d[1][i] = i;
}
for(int i = 1;i<=K;i++){
d[i][0] = 0;
d[i][1] = 1;
}
for (int i = 2;i<=N;i++){
for (int j = 2;j<=K;j++){
for (int k = 1;k<=i;k++){
d[j][i] = Math.min(d[j][i],Math.max(d[j-1][k-1], d[j][i-k])+1);
}
}
}
return d[K][N];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
int n = in.nextInt();
Solution solution = new Solution();
System.out.println(solution.superEggDrop(k,n));
}
}
不过时间复杂度还是很大，O(KN^2),空间复杂度O(KN)
动态规划的优化
从状态转移方程来看，每一个dp(i,j)，都需要遍历i次找到一个\(x \in[1, i]\)才能找到最小值，如何才能更高效的找到最合适的x呢？
分析\(dp(n,k)\)可以知道，n越大，dp就越大，所以\(dp(x-1,k-1)\)斜率为正，\(dp(n-x,k)\)斜率为负，两者构成一个V型图像，存在一个最小值，通过二分查找，可以找到对应的x:
public class Solution{
int[][] d = null;
public int superEggDrop(int K, int N) {
if(d == null){
d = new int[K+1][N+1];
for (int i = 0;i<K+1;i++){
Arrays.fill(d[i],0);
}
}
if (K == 1 || N < 3) return N;
if (d[K][N]==0) {
int start = 1, end = N;
while (start + 1 < end){
int x = (start + end) / 2;
if(superEggDrop(K-1, x-1)<superEggDrop(K, N-x)){
start = x;
}else if (superEggDrop(K-1, x-1)>superEggDrop(K, N-x)){
end = x;
}else {
start = end = x;
}
}
d[K][N] = Math.min(Math.max(superEggDrop(K -1, start -1), superEggDrop(K, N - start)),
Math.max(superEggDrop(K-1, end -1), superEggDrop(K, N-end))) + 1;
}
return d[K][N];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
int n = in.nextInt();
Solution solution = new Solution();
System.out.println(solution.superEggDrop(k,n));
}
}
时间复杂度为O(KNlog(N)), 空间复杂度为O(KN)，d其实是一个稀疏矩阵，这里可以考虑使用HashMap来存储，这样空间复杂度会降低很多。
比二分查找更快的确定x
看了一些资料，有一个可O(1)确定x的方法。
固定住K之后，N越大，x的值也就越大，也就是V折线的最小值再往有移动。
public class Solution{
public int superEggDrop(int K, int N) {
int[] d = new int[N+1];
// when K = 1;
for (int i = 0;i<N+1;i++){
d[i] = i;
}
for(int k = 2;k<K+1;++k){
int[] d2 = new int[N+1];
d2[1] = 1;
int x = 1;
for (int n = 1;n<N+1;n++){
// update x;
while (x<n && Math.max(d[x-1], d2[n-x])>Math.max(d[x], d2[n-x-1])) x++;
d2[n] = 1+ Math.max(d[x-1], d2[n-x]);
}
d = d2;
}
return d[N];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
int n = in.nextInt();
Solution solution = new Solution();
System.out.println(solution.superEggDrop(k,n));
}
}
时间复杂度为O(KN),空间复杂度为O(N) 解法里提到了决策单调性
