前言

首先看一下这个题目,是Leetcode的第887题"鸡蛋掉落":

你将获得 `K` 个鸡蛋,并可以使用一栋从 `1` 到 `N`  共有 `N` 层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层 `F` ,满足 `0 <= F <= N` 任何从高于 `F` 的楼层落下的鸡蛋都会碎,从 `F` 楼层或比它低的楼层落下的鸡蛋都不会破。
每次*移动*,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 `X` 扔下(满足 `1 <= X <= N`)。
你的目标是**确切地**知道 `F` 的值是多少。
无论 `F` 的初始值如何,你确定 `F` 的值的最小移动次数是多少?

分析

这道题曾经是作为Google面试的一道题目,不过当时问的是:一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?

因为有两个鸡蛋,所以我们可以考虑粗调和细调,即通过第一个鸡蛋的试错来缩小答案的范围。比如第一个鸡蛋在k层碎了,那么我们就可以确定临界楼层是\([1,k)\)之间;所以我们首先考虑的应该就是第一个鸡蛋应该在哪里扔

假设第一个鸡蛋的楼层策略是\(k_{1},k_{2},k_{3}....k_{p}\),其中p是扔的总次数,楼高为N

记录Leetcode 鸡蛋掉落 的思路-LMLPHP

第二个鸡蛋肯定是在\(k_{i}\)之间进行遍历,所以优化这个问题就是求一个策略组合使得p的值最小。举个例子,如果我们用二分法,选了k1=50扔,没有碎,好的我们进入下一个状态,取k2=75,仍然没有碎,进入下一个状态k3=90,碎了,说明临界不碎楼层是在\([76,89]\)之间的,我们总共实验了3+14=17次。我们这里选用二分法的k1、k2、k3就是一种可选的策略,换成其他的也可以,但是要使这个策略的p尽量的小就是我们的目标。

所以我们再仔细观察一下上图,发现小圆圈其实都是第二个鸡蛋遍历的过程,都是O(n),所以可以等价为一个操作,这个图实际上也就是一个树形结构:

记录Leetcode 鸡蛋掉落 的思路-LMLPHP

如果这个树类似下面的结构的话,我们可以得到最优解:

记录Leetcode 鸡蛋掉落 的思路-LMLPHP

我们的树结构最好满足的关系为:

记录Leetcode 鸡蛋掉落 的思路-LMLPHP

我们来解析一下第一个式子:\(k_{1}=k_{2}-k_{1}+1\),这是因为\(k_{1}-1=(k_{2}-k_{1}-1)+1\),加1是因为k2这个节点。要满足每棵子树的树高相等,\(k_{p}\)必须是一个递减等差数列。所以我们可以令\(k_{p}\sim N\),所以就有\(\frac{k_{1}(k_{1}+1)}{2}=N\)

回到Google这道面试题上来的话,就是\(\frac{x()(x+1)}{2}=200\),解得\(x=14\),所以扔蛋的一种策略为14,27,39,50,60,69,77,84,90,95,99,一共需要尝试11+(13+12+11+10+9+8+7+6+5+4)/10=11+8.5 -->=20次。

然后再回到Leetcode这道题上来,这道题用动态规划来做可能更加简便,当然用我们刚才分析这道题的树形结构来分析也是可以的。

动态规划

首先的先暂时抛开我们刚才树形结构的分析,这里先不讨论粗调与细调的概念,就是一个线性结构:

思路1

我们需要求一个最优决策使得扔的次数最小,虽然实际扔的次数会随着真实结果而变化,但是k个鸡蛋来测N层可以借助于k-1个鸡蛋测N层的结果。

我们用dp[n][k]表示k个鸡蛋测n层的扔的次数。如果i层的时候鸡蛋碎了,剩下来的k-1个鸡蛋用来测i-1层,也就是dp[n][k]=dp[i-1][k-1]+1;如果i层的时候鸡蛋没有碎,那么剩下来的k个鸡蛋用来测n-i个楼层。所以,在第i层扔,会用 max(dp[i-1][k-1], dp[n-i][k]) + 1 ,即$$dp[n][k] = min(max(dp[i-1][k-1], dp[n-i][k]) + 1 ) (1 <= i <= n)$$

思路2:

我们可以改变一下求解的思路,求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)

先给出代码:

class Solution {
public:
int superEggDrop(int K, int N) {
if(K==0) return 0;
if(K==1) return N;
int dp[N+2][K+2];
memset(dp,0,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=N;++i)
{
dp[i][0]=0;
for(int j=1;j<=K;++j)
{
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1;
if(dp[i][j]>=N)
return i;
}
}
return N;
}
};

树形结构

我们仍然可以从树形结构的角度去想,即尽量的把鸡蛋的数量往2上面去接近,扔一个鸡蛋数量就少一个;而这个思路其实是和动态规划思路1是一致的。

在知乎上也有关于这道题的讨论,见这里

05-12 18:22