[leetcode]887-鸡蛋掉落

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
606
文章
12
评论
2020年2月13日22:56:32 评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/super-egg-drop

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

示例 1:

  • 输入:K = 1, N = 2
  • 输出:2
  • 解释:鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。如果它没碎,那么我们肯定知道 F = 2 。因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2:

  • 输入:K = 2, N = 6
  • 输出:3

示例 3:

  • 输入:K = 3, N = 14
  • 输出:4

提示:

  • 1 <= K <= 100
  • 1 <= N <= 10000

二、动态规划+递归

看到题目的第一眼就能想到得用动态规划来解题了,关键是如何来定义动态规划的状态和状态转移方程。

比较容易想到的是以dp(k, n)来表示k个鸡蛋在n层建筑时需要扔鸡蛋的最小次数,它的最优状态肯定是从前面的1-n层楼中取,谁的状态越优,就取谁的。也就是说,在那一层扔鸡蛋需要的次数最少,就是谁。那么:

$$dp(k,n)=min(dp(k,1), dp(k,2), ..., dp(k,n))$$

在第i层扔鸡蛋,有两种结果:

  1. 鸡蛋碎了,这个时候鸡蛋少了一个,楼层也少一个,此时它的最优解是dp(k-1,i-1) + 1。
  2. 鸡蛋没碎,这个时候鸡蛋没少,楼层少了一个,最优解是dp(k,n-i) + 1。

可以参考这张图片:

[leetcode]887-鸡蛋掉落

图片来源:labuladong

后面的dp[k][n]和dp(k, n)是一个意思。

为什么没碎之后是dp[k][n-i],因为没碎的话,鸡蛋还是k个,而楼层只有n-i了,所以只要找出dp[k][n-i]就可以了。

计算出来这两种情况后,要选择最坏情况下的场景,所以要取两者的最大值。总结出来状态转移方程就是:

\(\begin{equation} dp[k][i]= \begin{cases} 1 & k=1 \\ 0 & n=0\\ max(dp[k-1][i-1], dp[k][n-i]) & k>1,n>0 \end{cases}\end{equation}\)

归纳成C++代码:

时间复杂度

计算所有的鸡蛋+楼层组合需要时间复杂度O(KN),每个楼层取最优值是O(N),总体的时间复杂度是:

$$O(K*N^2)$$

这个时间复杂度还是很大的,可以说迄今为止我还没见过这么高复杂度的动态规划。提交后果然超时了:

[leetcode]887-鸡蛋掉落

在本地测试这组数据发现需要执行2s+才能计算出来(CPU是I5-8400主频2.8GHz),所以提交肯定会超时:

[leetcode]887-鸡蛋掉落

三、动态规划+二分

超时之后不得不想办法优化,优化前为了确定在哪个楼层扔鸡蛋最优不得不从1遍历到n,这个时间复杂度是O(N)太长了,实际上可以使用二分法来找出最优解,讲O(N)变成O(logN)。

上面已经求出了状态转移方程是max(dp[k-1][i-1], dp[k][n-i]),其中可以知道的是,dp[k-1][i-1]是随着i逐步递增的,因为楼层越高,需要扔的次数肯定也越多。而dp[k][n-i]是跟随i递减的,因子i是负数,i越大,n-i越小,扔的次数也越小。

上面的状态转移方程就是现在所有楼层的最大值中,找到最小值,如图所示:

[leetcode]887-鸡蛋掉落

红色的线表示的是两个子状态中的最大值,两根线的交点正好就是所有最大值中的最小值。那么根据这个规律,就可以把i∈[1, n]的遍历改成二分法来遍历,找到这个最小值。代码如下:

修改后再测试上面超时的数据,只要4毫秒就可以执行完了,效率提高了几百倍:

[leetcode]887-鸡蛋掉落

再次提交代码,通过了(耗时较高):

[leetcode]887-鸡蛋掉落

把遍历变成二分后,遍历的O(N)变成了O(logN),所以总的时间复杂度是:O(KN*logN)​,空间复杂度是O(KN)。

四、终极动态规划

dp[k][m]表示k个鸡蛋扔m次最多可以确定的多少层的楼,那么第一个大于等于n的下标m就是扔鸡蛋的次数了。到第i层的时候,依旧是有两种策略:

  1. 鸡蛋碎了,此时鸡蛋减1,扔的次数减1,接下来可以检测出来的楼层是dp[k-1][m-1]
  2. 鸡蛋没碎,扔的次数减1,接下来可以检测出来的楼层是dp[k][m-1]

所以第i个鸡蛋能确定的楼层的总数是:dp[k-1][m-1] + dp[k][m-1] + 1,即鸡蛋碎了的时候能确定的楼层数加上鸡蛋没碎的时候能确定的楼层数再加上本层。

代码:

要注意的地方是循环条件终止条件是v[k][j-1] >= n,为什么是j-1呢,因为第一层for循环的j表示的是第j次扔鸡蛋能确定的层数,此时层数还没有确定,还要在下面的循环中计算得到。如果使用v[k][j]会出现死循环导致数据溢出。

时间复杂度O(K*N),提交后执行用时大大减少:

[leetcode]887-鸡蛋掉落

继续优化

上面已经计算出来状态转移方程是:

$$dp[k][i]=dp[k-1][i-1] + dp[k][i-1] + 1$$

可以看到,当前状态实际上只与前面一列的状态有关,可以只保存前面一列状态的数据,空间复杂度为O(K)。

[leetcode]887-鸡蛋掉落

马谦马谦马谦
  • 本文由 发表于 2020年2月13日22:56:32
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/leetcode887-super-egg-drop.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: