vlambda博客
学习文章列表

面试题-双蛋问题(动态规划)

肺炎疫情期间,在B站上看了李永乐老师关于双蛋问题的视频,刚好我最近写了一篇关于动态规划的文章,这里我们试着使用动态规划的思想简单分析下这个问题。

一、问题描述

有一座100层的楼,有一个鸡蛋,在低楼层的时候将鸡蛋扔下不会碎,但是高楼层扔下会碎。存在一个临界楼层从该楼层之上抛下来,鸡蛋一定会碎。现在有N个鸡蛋可以做检查(鸡蛋没碎可以重复使用,但是碎了就不能使用了),问最少几次(M)能够找到这个临界楼层。

二、尝试

1)假设N=1,为了确保鸡蛋不会碎,只能从第一层开始往上扔,直到鸡蛋碎了为止,最差M=100

2)假设鸡蛋有无限多,可以使用二分法来解决这个问题,即在第50层往下扔,如果鸡蛋碎了就在25层继续扔,如果没碎的话,在75层往下扔。依次类推,直到找到为止。2^M>=100,m约等于6.64

如果N=2的情况下,最好需要多少次才能试出M?

1)假设第一个鸡蛋每隔十层扔一次,10、20、30。。。100,等鸡蛋碎着之后从再从区间内开始尝试,如果在第100层碎了的话就是91-99,这样就可以试出临界楼层了。

临界楼层出现在100层碎掉的话最坏的情况就是先扔10次(100/10=10)然后在91、92、93.。。99层向下扔,M=10+9=19。临界楼层出现在10层碎掉的话最坏的情况就是先扔1次(10/10=1),然后在1、2、3。。。9层向下扔要10次,M=1+9=10

当然我们可以通过扩大、减小第一次扔鸡蛋相隔楼层的数可以减少第二次扔鸡蛋的次数,但是这种情况计算出的结果也并不一定就是最优解,所以我们可以引入动态规划的思量来解决这个问题。

三、动态规划

假设有t层楼和n个鸡蛋,我们要如何计算出这个问题呢?

设M(t,n)为在从t层楼,n个蛋的情况下需要抛投的最少次数,假设在k层楼进行抛投,会产生两种情况:

如果鸡蛋碎了,那么我们需要继续计算的就是M(k, n-1)(n-1是因为鸡蛋碎了)

如果鸡蛋没碎,那么我们需要继续计算的就是M(t-k, n)

因为我们需要找到最坏的情况,所以我们需要去两者中的最大值

因此我们可以得出,在k层扔下第一颗鸡蛋Mk(t,n) = max(M(k-1, n-1), M(t-k, n)) + 1

k值可能为1-t次,因此想要找抛投的最少次数为M(t,n)= min(M1(t,n), M2(t,n), M3(t,n) ...... Mk(t,n))

在t=1或者n=1的时候,我们能够清楚的计算出M(t,n),这就是该问题的边界。

有了边界和状态转移公式,我们就可以通过代码实现这个问题

public static int getMin(int t, int n) {
int[][] dp = new int[t + 1][n + 1];

// 边界处理,只有一个鸡蛋,i层就要扔i次
for (int i = 1; i < t + 1; i++) {
dp[i][1] = i;
}

// 边界处理,只有一层,不论鸡蛋有几个只要扔一次就可以
for (int j = 1; j < n + 1; j++) {
dp[1][j] = 1;
}

for (int i = 2; i < t + 1; i++) {
for (int j = 2; j < n + 1; j++) {
int min = Integer.MAX_VALUE;
for (int k = 1; k < i; k++) {
min = Math.min(min, Math.max(dp[i - k][j], dp[k - 1][j - 1]) + 1);
}
dp[i][j] = min;
}
}

return dp[t][n];
}