当前位置:   article > 正文

鸡蛋掉落(动态规划)_算法设计与分析实验四动态规划鸡蛋掉落问题实验,1、给出解决问题的动态规划方程;

算法设计与分析实验四动态规划鸡蛋掉落问题实验,1、给出解决问题的动态规划方程;

问题来源力扣算法面试汇总

问题描述:你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

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

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

# 输入
K = 1
N = 2
  • 1
  • 2
  • 3

以下分析内容主要参考题解中@labuladong的解答。

分析:一般这种带有生活场景的题目,都是要用动态规划

  • 问题目标:最坏情况下的最小移动次数。

解释:

  • 对于我们如何选择楼层进行测试,是有很多种选择或者策略的。比如,我们可以选择依次从1层到最高层扔鸡蛋;或者每次选择从中间楼层扔鸡蛋。

  • 每个策略下,都有最好的情况或者最坏的情况。比如,依次从1层扔到最高层,最好的情况是在第一层就发现鸡蛋碎了,这样就只扔一次;但最坏的情况下,我们一直扔到最高层才发现鸡蛋碎了,这样就要扔N次。

  • 最坏情况下的最小移动次数,就是要找最佳策略,使得这个策略下,最坏情况在所有策略中是最小的。

上面我们确定了问题,接下来用动态规划来解决。对于动态规划,我们要确定两点,即问题的状态和选择。

  • 问题的状态:当前鸡蛋总数K和楼层总数N
  • 选择:选择楼层X来扔鸡蛋。显然, 1 ≤ X ≤ N 1\le X\le N 1XN

这样,我们初步的动态规划框架为

# 当前状态为K个鸡蛋,N层楼
# 返回这个状态下最优结果
def dp(K, N):
	int res
	for 1<=X<=N:
		res = min(res, 在第X层楼上扔鸡蛋的结果)
	return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

这个时候,在第X层楼上扔鸡蛋的结果如何表示?在第X层楼上扔鸡蛋,

  • 如果鸡蛋没碎,那么接下来应该测试第X+1层楼至第N层楼,这样,子问题的状态就变成K个鸡蛋,N-X层楼,结果为 d p ( K , N − X ) dp(K, N-X) dp(K,NX)
  • 如果鸡蛋破碎,那么接下来应该测试第1层楼至第X-1层楼,这样,子问题的状态就变成K-1个鸡蛋,X-1层楼,结果为 d p ( K − 1 , X − 1 ) dp(K-1,X-1) dp(K1,X1)
  • 由于我们要选择最坏情况,所以我们在第X层楼上扔鸡蛋的结果应该是 m a x ( d p ( K , N − X ) , d p ( K − 1 , X − 1 ) ) + 1 max(dp(K, N-X), dp(K-1,X-1))+1 max(dp(K,NX),dp(K1,X1))+1

所以我们的程序为

# 当前状态为K个鸡蛋,N层楼
# 返回这个状态下最优结果
def dp(K, N):
	for 1<=X<=N:
		res = min(res, max(dp(K, N-X), dp(K-1,X-1))+1)
	return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

接下来,递归的base case为

  • K = 1 K=1 K=1,即只有一个鸡蛋时,只能从最底层往上遍历,因此, d p ( 1 , N ) = N dp(1, N)=N dp(1,N)=N
  • N = 1 N=1 N=1,即只有一层楼时,无论有多少鸡蛋都只需要测试一次,因此, d p ( K , 1 ) = 1 dp(K, 1)=1 dp(K,1)=1

我们添加一个备忘录memo以防止重复计算,即

# 当前状态为K个鸡蛋,N层楼
# 返回这个状态下最优结果
def dp(K, N):
	if K == 1: return N
	if N == 1: return 1
	memo = {}
	if (K, N) in memo:
		return memo[(K, N)]
	res = float('inf')
	for 1<=X<=N:
		res = min(res, max(dp(K, N-X), dp(K-1,X-1))+1)
	memo[(K, N)] = res
	return res
	
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/621342
推荐阅读
相关标签
  

闽ICP备14008679号