写点什么

[Day15]-[动态规划] 鸡蛋掉落

作者:方勇(gopher)
  • 2022 年 4 月 14 日
  • 本文字数:935 字

    阅读完需:约 3 分钟

887. 鸡蛋掉落

难度困难 780 收藏分享切换为英文接收动态反馈

给你 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
复制代码


题解:

func superEggDrop(k int, n int) int {	var solution func(K, N int) int	var key func(K, N int) string	var dp = make(map[string]int)	var min func(x, y int) int	// var max func(x, y int) int	key = func(K, N int) string {		return strconv.Itoa(K) + "_" + strconv.Itoa(N)	}
min = func(x, y int) int { if x < y { return x } return y }
// max = func(x, y int) int { // if x > y { // return x // } // return y // }
solution = func(K, N int) int { if K == 1 { return N } if N == 0 { return 0 } if v, ok := dp[key(K, N)]; ok { return v } res := math.MaxInt // for i := 1; i <= N; i++ { // res = min(res, max(solution(K, N-i), solution(K-1, i-1))+1) // } lo, hi := 1, N for lo <= hi { mid := (lo + hi) / 2 broker := solution(K-1, mid-1) not_broker := solution(K, N-mid) if broker > not_broker { hi = mid - 1 res = min(res, broker+1) } else { lo = mid + 1 res = min(res, not_broker+1) } } dp[key(K, N)] = res return res }
return solution(k,n)}
复制代码


用户头像

Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入

我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!

评论

发布
暂无评论
[Day15]-[动态规划]鸡蛋掉落_LeetCode_方勇(gopher)_InfoQ写作平台