题目描述
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F
with 0 <= F <= N
such that any egg dropped at a floor higher than F
will break, and any egg dropped at or below floor F
will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X
(with 1 <= X <= N
).
Your goal is to know with certainty what the value of F
is.
What is the minimum number of moves that you need to know with certainty what F
is, regardless of the initial value of F
?
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
Note:
1 <= K <= 100
1 <= N <= 10000
题意:你将获得 K
个鸡蛋,并可以使用一栋从 1 到 N
共有 N
层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层F
,满足0 <= F <= N
任何从高于F
的楼层落下的鸡蛋都会碎,从F
楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层X
扔下(满足 1 <= X <= N
)。
你的目标是确切地知道 F
的值是多少。
无论F
的初始值如何,你确定F
的值的最小移动次数是多少?
算法1
(动态规划) $O(KN^2)$
接下来我们考虑两个鸡蛋,假设我们任选一层k
扔下去,那么有两种情况,鸡蛋碎了或者鸡蛋没碎:
- 如果鸡蛋碎了,这意味着,我们需要在只剩一个鸡蛋的情况下,找到在
[1,k-1]
中的答案,根据上面的讨论,那么我们还需要k - 1
步。 - 如果鸡蛋没碎的话,那么意味着我们还有两个鸡蛋,需要在
[k + 1,N]
中找到答案,我们需要观察到很重要的一点,那就是在[k + 1,N]
中找到答案其实是和在[1,N - K]
中找是一模一样的。
因为鸡蛋在k
层是否会碎是不确定的,所以我们必须要做好最坏的打算,即如果我们在k
层扔下鸡蛋,最坏情况下我们需要1 + max(dp[1][k - 1],dp[2][N - k])
。另一方面我们需要希望移动步数尽可能小,所以我们需要考虑1 <= k <= N
,来找到最优的k
使得其对应的1 + max(dp[1][k - 1],dp[2][N - k])
最小。
那么状态转移方程就显而易见了:
$$
dp[i][j] = \min \limits_{1\leq k\leq j} 1 + max(dp[i-1][k-1],dp[i][j-k])
$$
另一方面我们考虑一下状态初始化,即我们只有一颗鸡蛋的时候:
$$
dp[1][j] = j
$$
此外,我们还需要对于任意的dp[i][j]
,其上界等于j
,因为即使我们只有一个鸡蛋我们也最多只需要j
步。
基于上述讨论,我们可以给出代码如下:
int superEggDrop(int K, int N) {
int dp[K + 1][N + 1];
memset(dp,0x3f,sizeof(dp));
for(int i = 0 ; i <= N ; i ++)
dp[1][i] = i;
for(int i = 2 ; i <= K ; i ++)
{
for(int j = 1 ; j <= N ; j ++)
{
dp[i][j] = j;
for(int k = 1 ; k <= j ; k ++)
dp[i][j] = min(dp[i][j],1 + max(dp[i - 1][k - 1],dp[i][j - k]));
}
}
return dp[K][N];
}
显然,其时间复杂度为$O(KN^2)$,在这一题的数据范围是无法求解的,虽然我们并没有10000层高的大楼。我们需要对上述方法进行优化。
算法2
(考虑最优策略的动态规划) $O(NK)$
假设我们需要求出:
$$
dp[i][j] = \min \limits_{1\leq k\leq j} 1 + max(dp[i-1][k-1],dp[i][j-k])
$$
假设我们有一个最优的楼层选择$x$,我们可以发现当$i$固定的时候,最优策略$x$是随着$j$的增大而单调递增的,所以我们在枚举$j$的时候,类似于双指针,我们让候选$x$从$dp[i][j - 1]$最优的策略开始枚举即可。
另一方面,我们可以发现$dp[i-1][k-1]$是随着$k$单调递增的,$dp[i][j-k]$是随着$k$单调递减的,那么二者最大值则是随着$k$先减小后增大的,所以我们只需要枚举$x$找到最低点,那么就一定是最优解。
int superEggDrop(int K, int N) {
int dp[K + 1][N + 1];
memset(dp,0x3f,sizeof(dp));
for(int i = 0 ; i <= N ; i ++)
dp[1][i] = i;
for(int i = 2 ; i <= K ; i ++)
{
int x = 1;//x随着j单调递增。
for(int j = 0 ; j <= N ; j ++)
dp[i][j] = j;
for(int j = 1 ; j <= N ; j ++)
{
// 找到第一个拐点,就是当前的最优解。
while(x < j && max(dp[i - 1][x - 1],dp[i][j - x]) > max(dp[i - 1][x],dp[i][j - x - 1]))
x ++;
dp[i][j] = 1 + max(dp[i - 1][x - 1],dp[i][j - x]);
}
}
return dp[K][N];
}
对于上面的二维数组我们可以使用滚动数组来优化成一维的:
int superEggDrop(int K, int N) {
int dp[N + 1];
for(int i = 0 ; i <= N ; i ++)
dp[i] = i;
for(int i = 2 ; i <= K ; i ++)
{
int temp[N + 1] = {};
int x = 1;
for(int j = 1 ; j <= N ; j ++)
{
while(x < j && max(dp[x - 1],temp[j - x]) > max(dp[x],temp[j - x - 1]))
x ++;
temp[j] = 1 + max(dp[x - 1],temp[j - x]);
}
memcpy(dp,temp,sizeof(dp));
}
return dp[N];
}
算法3
(另一种动态规划) $O(KlogN)$
考虑我们将鸡蛋在$t$层扔下,那么有两种情况:
- 鸡蛋碎了,那么我们可以使用
i - 1
步和j - 1
个鸡蛋去检测下面的位置,同时上面不管有多少层我们都可以检测到是不符合要求的。 - 鸡蛋没碎,那么我们可以使用
i - 1
步和j
个鸡蛋去检测上面的位置,我们同时可以确认其下面及其自身的t
层也不是答案了。
我们注意到,如果出现一次鸡蛋碎了,那么其最多可以确认无数层,如果鸡蛋没有碎,那么其最多可以确认dp[i - 1][j] + t
层。考虑最坏情况,我们认为我们最多只可以确认dp[i - 1][j] + t
层,那么t
最大是多少呢?
dp[i - 1][j - 1] + 1
,这是因为,如果在更高的t‘
扔下鸡蛋并且碎了的话,我们剩余的i - 1
步内使用j - 1
个鸡蛋无法确认其解。
另一种思考思路:
int superEggDrop(int K, int N) {
int dp[N + 1][K + 1] = {};
for(int i = 1 ; i <= N ; i ++)
{
for(int j = 1 ; j <= K ; j ++)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1;
if(dp[i][j] >= N)
return i;
}
}
return 0;
}
上述代码可以优化成一维数组:
int superEggDrop(int K, int N) {
int dp[K + 1] = {};
for(int i = 1 ; i <= N ; i ++)
{
for(int j = K ; j > 0 ; j --)
{
dp[j] = dp[j - 1] + dp[j] + 1;
if(dp[j] >= N)
return i;
}
}
return 0;
}
“如果出现一次鸡蛋碎了,那么其最多可以确认无数层”,请问为什么能确定无数层?
最后一种的时间复杂度应该是O(KN)
学习了,很全面~~