[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)}

复制代码

发布于: 刚刚阅读数: 2

方勇(gopher)

关注

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

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

发布

暂无评论

创作场景

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

887. 鸡蛋掉落

方勇(gopher)

评论