高楼扔鸡蛋_高楼扔鸡蛋python

将题目抽象一下，就是如何获取某个元素在有序数组中的位置。这样就很容易的想到用二分法去解决。

但考虑到扔鸡蛋这个问题是寻找元素位置的异化，鸡蛋的数量是有限。在某种情况下鸡蛋的数量会小于logN所以不能全使用二分法进行解决。

所以可以考虑使用动态规范来进行解决问题:

动态规划一般需要考虑两个问题

1 是找到能代表问题的状态

在这个题目中很明显当前拥有的鸡蛋数 K 和需要测试的楼层数 N 就是问题所代表的状态

2 是找到问题之间的递推公式

而每在第i层扔一个鸡蛋，状态都会发生相应的转移
容易根据dp公式得出递归代码

递归版本（超时了）

public int superEggDrop(int K, int N) {
    if (K == 1) {
        return N;
    }
    if (N == 0){
        return 0;
    }
    int res=Integer.MAX_VALUE;
    for(int i=1;i<N+1;i++){
        res=Math.min(res,Math.max(superEggDrop(K,N-i),superEggDrop(K-1,i-1)));
    }
    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代版本（也超时了）

class Solution {
    public int superEggDrop(int k, int n) {
        int max=Math.max(k,n);
        int[][] dp=new int[k+2][n+2];


        for(int i=0;i<=k;i++){
            dp[i][1]=1;
            dp[i][0]=0;
        }
        for(int i=0;i<=n;i++){
            dp[1][i]=i;
        }


        for(int i=2;i<=k;i++){
            for(int j=2;j<=n;j++){
                dp[i][j]=Integer.MAX_VALUE;
                for(int a=1;a<=j;a++){
                    dp[i][j]=Math.min(dp[i][j],Math.max(dp[i-1][a-1],dp[i][j-a])+1);
                }
            }
        }
        return dp[k][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

我们可以改变一下求解的思路，求k个鸡蛋在m步内可以测出多少层：
假设: dp[k][m] 表示k个鸡蛋在m步内最多能测出的层数。
那么，问题可以转化为当 k <= K 时，找一个最小的m，使得dp[k][m] <= N。

我们来考虑下求解dp[k][m]的策略：
假设我们有k个鸡蛋第m步时，在第X层扔鸡蛋。这时候，会有两种结果，鸡蛋碎了，或者没碎。
如果鸡蛋没碎，我们接下来会在更高的楼层扔，最多能确定 X + dp[k][m-1] 层的结果；
如果鸡蛋碎了，我们接下来会在更低的楼层扔，最多能确定 Y + dp[k-1][m-1] 层的结果 (假设在第X层上还有Y层)。
因此，这次扔鸡蛋，我们最多能测出 dp[k-1][m-1] (摔碎时能确定的层数) + dp[k][m-1] (没摔碎时能确定的层数) + 1 (本层) 层的结果。
另外，我们知道一个鸡蛋一次只能测一层，没有鸡蛋一层都不能测出来。
因此我们可以列出完整的递推式:
dp[k][0] = 0
dp[1][m] = m (m > 0)
dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 (k > 0, m>0)

代码:

// NOTE: 第一维和第二维换了下位置
int superEggDrop(int K, int N) {
    int dp[N+2][K+2];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 0;
    for (int m = 1; m <= N; m++) {
        dp[m][0] = 0;
        for (int k = 1; k <= K; k++) {
            dp[m][k] = dp[m-1][k] + dp[m-1][k-1] + 1;
            if (dp[m][k] >= N) {
                return m;
            }
        }
    }
    return N;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16