赞
踩
链接:leetcode-887-鸡蛋掉落
给你 k 枚相同的鸡蛋,并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ,满足 0 <= f <= n ,任何从 高于 f 的楼层落下的鸡蛋都会碎,从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作,你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下(满足 1 <= x <= n)。如果鸡蛋碎了,你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎,则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 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
for j in range(1, n+1):
res = float("INF")
for h in range(1, j+1):
res = min(res, max(dp[i][j-h], dp[i-1][h-1])+1)
#加1是因为我们人了一次,进行了一次尝试
dp[i][j] = res
res = min(res, max(dp[i][j-h], dp[i-1][h-1])+1)
这是一个最大值最小化问题,可以用二分查找
首先明确一点,dp[i]这一层的值是一个递增的序列dp[i][j] <= dp[i][j+c] (c>0)
class Solution: def superEggDrop(self, k: int, n: int) -> int: """ dp(k, n) n层k个鸡蛋最少需要移动多少次 """ dp = [[0]*(n+1) for _ in range(k+1)] dp[1][:] = range(0, n+1) for i in range(2, k+1): for j in range(1, n+1): res = float("INF") # for c in range(1, j+1): # res = min(res, max(dp[i][j-c], dp[i-1][c-1])+1) kNN复杂度 l, r = 1, j while(l <= r): m = (l+r) // 2 if dp[i][j-m] > dp[i-1][m-1]: l = m + 1 res = min(res, dp[i][j-m]) + 1 elif dp[i][j-m] < dp[i-1][m-1]: r = m - 1 res = min(res, dp[i-1][m-1]) + 1 else: res = dp[i-1][m-1] + 1 break # res = min(res, max(dp[i][j-m], dp[i-1][m-1])+1) dp[i][j] = res return dp[k][n]
原题目求的是k个鸡蛋N层最少需要操作多少次才可以确定f。
转换一下: 求k个鸡蛋最多移动f次,求N的最大值
表示: dp[i][j]: 表示i个鸡蛋,最多移动j次的最大值N
初始状态:
状态转移:
dp[k][f]:如果有k个蛋,可以操作f次,所能确定的楼层
dp[k][f-1]:操作一次后还剩f-1次,蛋碎或者没碎。碎了还有k-1个蛋,没碎还有k个蛋就变成dp[k-1][f-1]
dp[k][f] = dp[k][f-1] + dp[k-1][f-1] +1
1:是在某一层掷出,其实我没太懂加1的具体,有点抽象
dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
f = 0
while dp[k][f] < n:
f += 1
for i in range(1, k+1):
dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
return f
dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
第f列只用到了f-1列的数据,所以可以用一维数组
dp = [0 for i in range(k+1)]
f = 0
while dp[k] < n:
for i in range(k, 0, -1):
dp[i] = dp[i] + dp[i-1] + 1
f += 1
return f
至于为什么从后向前遍历:简单解释下
for i in range(k, 0, -1): dp[i] = dp[i] + dp[i-1] + 1
对比一下
dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
dp[i] = dp[i] + dp[i-1] + 1
如果从前向后 ,当i变成i+1时
dp[i+1][f] = dp[i+1][f-1] + dp[i][f-1] + 1 dp[i+1] = dp[i+1] + dp[i] + 1 """ 从前往后问题出在这儿的 dp[i]应该对应二维dp[i][f-1]的值 现在的dp[i]是已经更新的 dp[i] = dp[i] + dp[i-1] + 1 dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1 不在单纯是dp[i][f-1]的值了,被覆盖了 """ """ 我们看看从后向前,i变成i-1 dp[i-2]的值应该对应二维dp[i-2][f-1] 而由于从后向前遍历,dp[i-2]的值并没有变化过,所以这里还是对应的二维数组中dp[i-2][f-1] """ dp[i-1][f] = dp[i-1][f-1] + dp[i-2][f-1] + 1 dp[i-1] = dp[i-1] + dp[i-2] + 1
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。