标签搜索

目 录CONTENT

文章目录

鸡蛋掉落.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 8 阅读 / 8,050 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

鸡蛋掉落

@[toc]

一、问题描述

你将获得 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. 1 <= K <= 100
  2. 1 <= N <= 10000

二、解析题⽬

  1. 题⽬是这样: 你⾯前有⼀栋从 1 到 N 共 N 层的楼, 然后给你 K 个鸡蛋( K ⾄少为 1) 。 现在确定这栋楼存在楼层 0 <= F <= N , 在这层楼将鸡蛋扔下去, 鸡蛋恰好没摔碎(⾼于 F 的楼层都会碎, 低于 F 的楼层都不会碎) 。 现在问你,最坏情况下, 你⾄少要扔⼏次鸡蛋, 才能确定这个楼层F 呢?
  2. 也就是让你找摔不碎鸡蛋的最⾼楼层 F , 但什么叫「最坏情况」 下「⾄少」 要扔⼏次呢? 我们分别举个例⼦就明⽩了
  3. ⽐⽅说现在先不管鸡蛋个数的限制, 有 7 层楼, 你怎么去找鸡蛋恰好摔碎的那层楼F?
  4. 最原始的⽅式就是线性扫描: 我先在 1 楼扔⼀下, 没碎, 我再去 2 楼扔⼀下, 没碎, 我再去 3 楼……以这种策略,最坏情况应该就是我试到第 7 层鸡蛋也没碎( F = 7 ) , 也就是我扔了 7 次鸡蛋
  5. 先在你应该理解什么叫做「最坏情况」 下了, 鸡蛋破碎⼀定发⽣在搜索区间穷尽时, 不会说你在第 1 层摔⼀下鸡蛋就碎了, 这是你运⽓好, 不是最坏情况。
  6. 现在再来理解⼀下什么叫「⾄少」 要扔⼏次。 依然不考虑鸡蛋个数限制, 同样是 7 层楼, 我们可以优化策略。
  7. 最好的策略是使⽤⼆分查找思路, 我先去第 (1 + 7) / 2 = 4 层扔⼀下:
  8. 如果碎了说明 F ⼩于 4, 我就去第 (1 + 3) / 2 = 2 层试……
  9. 如果没碎说明 F ⼤于等于 4, 我就去第 (5 + 7) / 2 = 6 层试…
  10. 以这种策略, 最坏情况应该是试到第 7 层鸡蛋还没碎( F = 7 ) , 或者鸡蛋⼀直碎到第 1 层( F = 0 ) 。 然⽽⽆论那种最坏情况, 只需要试 log7向上取整等于 3 次, ⽐刚才尝试 7 次要少, 这就是所谓的⾄少要扔⼏次。
  11. 实际上, 如果不限制鸡蛋个数的话, ⼆分思路显然可以得到最少尝试的次数, 但问题是, 现在给你了鸡蛋个数的限制 K , 直接使⽤⼆分思路就不⾏了。
  12. ⽐如说只给你 1 个鸡蛋, 7 层楼, 你敢⽤⼆分吗? 你直接去第 4 层扔⼀下,
  13. 如果鸡蛋没碎还好, 但如果碎了你就没有鸡蛋继续测试了, ⽆法确定鸡蛋恰好摔不碎的楼层 F 了。 这种情况下只能⽤线性扫描的⽅法, 算法返回结果应该是 7。
  14. 也许会有这种想法: ⼆分查找排除楼层的速度⽆疑是最快的,那⼲脆先⽤⼆分查找, 等到只剩 1 个鸡蛋的时候再执⾏线性扫描, 这样得到的结果是不是就是最少的扔鸡蛋次数呢?
  15. 很遗憾, 并不是, ⽐如说把楼层变⾼⼀些, 100 层, 给你 2 个鸡蛋, 你在 50层扔⼀下, 碎了, 那就只能线性扫描 1〜49 层了, 最坏情况下要扔 50 次
  16. 如果不要「⼆分」 , 变成「五分」 「⼗分」 都会⼤幅减少最坏情况下的尝试次数。 ⽐⽅说第⼀个鸡蛋每隔⼗层楼扔, 在哪⾥碎了第⼆个鸡蛋⼀个个线性扫描, 总共不会超过 20 次​。最优解其实是 14 次。 最优策略⾮常多, ⽽且并没有什么规律可⾔

三、 思路分析

对动态规划问题, 直接套框架即可: 这个问题有什么「状态」 ,有什么「选择」 , 然后穷举

状态」 很明显, 就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N 。 随着测试的进⾏, 鸡蛋个数可能减少, 楼层的搜索范围会减⼩, 这就是状态的变化。

选择」 其实就是去选择哪层楼扔鸡蛋。 回顾刚才的线性扫描和⼆分思路,

⼆分查找每次选择到楼层区间的中间去扔鸡蛋, ⽽线性扫描选择⼀层层向上测试。 不同的选择会造成状态的转移。

现在明确了「状态」 和「选择」 , 动态规划的基本思路就形成了: 肯定是个⼆维的 dp 数组或者带有两个状态参数的 dp 函数来表⽰状态转移(dp[K][N]代表一共k个鸡蛋N层楼,来进行测试); 外加⼀个 for 循环来遍历所有选择, 择最优的选择更新状态:

# 当前状态为 K 个鸡蛋, ⾯对 N 层楼
# 返回这个状态下的最优结果
def dp(K, N):
	int res
	for 1 <= i <= N:
		res = min(res, 这次在第 i 层楼扔鸡蛋)
return res

我们选择在第 i 层楼扔了鸡蛋之后,可能出现两种情况:鸡蛋碎了,鸡蛋没碎。 注意,这时候状态转移就来了:

如果鸡蛋碎了那么鸡蛋的个数 K 应该减⼀,搜索的楼层区间应该从[1..N] 变为 [1..i-1] 共 i-1 层楼

如果鸡蛋没碎那么鸡蛋的个数 K 不变,搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼
在这里插入图片描述

因为我们要求的是最坏情况下扔鸡蛋的次数, 所以鸡蛋在第 i 层楼碎或者没碎, 取决于那种情况的结果更⼤

def dp(K, N):
	for 1 <= i <= N:
	# 最坏情况下的最少扔鸡蛋次数
		res = min(res,
		max(
			dp(K - 1, i - 1), # 碎
			dp(K, N - i) # 没碎
			) + 1 # 在第 i 楼扔了⼀次
			)
return res

递归的 base case 很容易理解:

当楼层数 N 等于 0 时, 显然不需要扔鸡蛋;
当鸡蛋数 K 为 1 时, 显然只能线性扫描所有楼层:

def dp(K, N):
if K == 1: return N
if N == 0: return 0
...

⾄此, 其实这道题就解决了! 只要添加⼀个备忘录消除重叠⼦问题即可:

def superEggDrop(K: int, N: int):
	memo = dict()
	def dp(K, N) -> int:
		# base case
		if K == 1: return N
		if N == 0: return 0
		# 避免重复计算
		if (K, N) in memo:
			return memo[(K, N)]
		res = float('INF')
		# 穷举所有可能的选择
		for i in range(1, N + 1):
			res = min(res,
					max(
						dp(K, N - i),
						dp(K - 1, i - 1)
						) + 1
					)
		# 记⼊备忘录
		memo[(K, N)] = res
	return res
return dp(K, N)

方法一:动态规划(不加备忘录肯定超时,所以直接加上)

class Solution {
public:
    int dp(int k,int n,int **& ret)
    {
        //当 k==1 只剩下一个鸡蛋的时候,我们就只能线性测试,即一层一层的测试,所以最坏情况下就是到达n层楼的顶部
        if(k == 1)
        {
            return n;
        }

        //当 n == 0 时,代表已经不用测试了,相当于你在地面测试,没有楼,搞个屁,直接return
        if(n == 0)
        {
            return 0;
        }

        //如果在备忘录中,直接返回,减去重复计算
        if(ret[k][n] != -2)
        {
            return ret[k][n];
        }

        int res = INT_MAX;

        for(int i = 1;i <= n;i++)
        {
            //逐层的测试,返回最后在最坏的情况下的最优解
            res = min(res,
                        max(dp(k - 1,i - 1,ret) + 1,//鸡蛋仍在第 i 层碎了,鸡蛋个数 -1,楼层从[1->n]变成[1->i-1]
                        dp(k,n - i,ret) + 1));//鸡蛋没碎,鸡蛋个数就不变,回收利用,楼层从[1->n]变成[i + 1 -> n]共n - i 层楼(因为求的是 无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少,所以不用关心具体的楼层,只是求你确定 K 的移动次数)
        }
        ret[k][n] = res;

        return ret[k][n];

    }
    int superEggDrop(int K, int N) {
        int Max = max(K,N) + 1;
        int ** ret = (int**)malloc(sizeof(int*) * Max);
        for(int i = 0;i < Max;i++)
        {
            ret[i] = (int*)malloc(sizeof(int) * Max);
        }

        for(int i = 0;i < Max;i++)
        {
            for(int j = 0;j < Max;j++)
            {
                ret[i][j] = -2;
            }
        }

        //这里为了方便就不释放ret了,非要释放就把结果保存一下就ok
        return dp(K,N,ret);
    }
};

他妹的,加上备忘录还超时,还得优化

方法二:优化动态规划(二分)

⾸先, 我们可能不理解代码中为什么⽤⼀个 for 循环遍历楼层 [1..N] ,也许会把这个逻辑和之前探讨的线性扫描混为⼀谈。 其实不是的, 这只是在做⼀次「选择」

⽐⽅说你有 2 个鸡蛋, ⾯对 10 层楼, 你这次选择去哪⼀层楼扔呢? 不知道, 那就把这 10 层楼全试⼀遍。 ⾄于下次怎么选择不⽤你操⼼, 有正确的状态转移, 递归会算出每个选择的代价, 我们取最优的那个就是最优解

⼆分的解法也有点误导性, 你很可能以为它跟我们之前讨论的⼆分思路扔鸡蛋有关系, 实际上没有半⽑钱关系。
简单介绍⼀下⼆分查找的优化吧, 其实只是在优化这段代码:

def dp(K, N):
	for 1 <= i <= N:
	# 最坏情况下的最少扔鸡蛋次数
		res = min(res,
					max(
						dp(K - 1, i - 1), # 碎
						dp(K, N - i) # 没碎
						) + 1 # 在第 i 楼扔了⼀次
				)
return res

⾸先我们根据 dp(K, N) 数组的定义(有 K 个鸡蛋⾯对 N 层楼, 最少需要扔⼏次)

很容易知道 K 固定时, 这个函数⼀定是单调递增的, ⽆论你策略多聪明, 楼层增加测试次数⼀定要增加

那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 这两个函数, 其中 i 是从 1到 N 单增的, 如果我们固定 K 和 N , 把这两个函数看做关于 i 的函数, 前者随着 i 的增加应该也是单调递增的, ⽽后者随着 i 的增加应该是单调递减的:
在这里插入图片描述

这时候求⼆者的较⼤值, 再求这些最⼤值之中的最⼩值, 其实就是求这个交点嘛, 熟悉⼆分搜索的同学肯定敏感地想到了, 这不就是相当于求Valley(⼭⾕) 值嘛, 可以⽤⼆分查找来快速寻找这个点的。

直接贴⼀下代码吧, 思路还是完全⼀样的:

def superEggDrop(self, K: int, N: int) -> int:
	memo = dict()
	def dp(K, N):
		if K == 1: return N
		if N == 0: return 0
		if (K, N) in memo:
			return memo[(K, N)]
		res = float('INF')
		# ⽤⼆分搜索代替线性搜索
		lo, hi = 1, N
		while lo <= hi:
			mid = (lo + hi) // 2
			broken = dp(K - 1, mid - 1) # 碎
			not_broken = dp(K, N - mid) # 没碎
		# res = min(max(碎, 没碎) + 1)
		if broken > not_broken:
			hi = mid - 1
		res = min(res, broken + 1)
		else:
			lo = mid + 1
		res = min(res, not_broken + 1)
		memo[(K, N)] = res
	return res
return dp(K, N)

C++代码

class Solution {
public:
    int dp(int k,int n,vector<vector<int>>& ret)
    {
        //当 k==1 只剩下一个鸡蛋的时候,我们就只能线性测试,即一层一层的测试,所以最坏情况下就是到达n层楼的顶部
        if(k == 1)
        {
            return n;
        }

        //当 n == 0 时,代表已经不用测试了,相当于你在地面测试,没有楼,搞个屁,直接return
        if(n == 0)
        {
            return 0;
        }

        //如果在备忘录中,直接返回,减去重复计算
        if(ret[k][n] != -2)
        {
            return ret[k][n];
        }

        int res = INT_MAX;

        int low = 1;
        int hight = n + 1;

        while(low < hight)
        {
            int mid = (low + hight) >> 1;

            int broken = dp(k - 1,mid - 1,ret);//碎
            int not_brokeb = dp(k,n - mid,ret);//没碎

            //选择碎或者没碎中最差的情况
            if(broken > not_brokeb)
            {
                hight = mid;//更新在鸡蛋碎的时候,相当于在mid的左边进行
                res = min(res,broken + 1);
            }
            else
            {
                //在鸡蛋没碎的时候,相当于在mid的右边进行,和dp函数的原理类似
                low = mid + 1;
                res = min(res,not_brokeb + 1);
            }

        }

        ret[k][n] = res;

        return ret[k][n];
    }
    int superEggDrop(int K, int N) {
        vector<vector<int>> ret(K + 1, vector<int>(N + 1, -2));

        return dp(K,N,ret);
    }
};


不能在堆上弄,容易超出内存限制,尴尬

方法三:二分法优化

⾸先简述⼀下原始动态规划的思路:

1、 暴⼒穷举尝试在所有楼层 1 <= i <= N 扔鸡蛋, 每次选择尝试次数最少的那⼀层;

2、 每次扔鸡蛋有两种可能, 要么碎, 要么没碎;

3、 如果鸡蛋碎了, F 应该在第 i 层下⾯, 否则, F 应该在第 i 层上⾯;

4、 鸡蛋是碎了还是没碎, 取决于哪种情况下尝试次数更多, 因为我们想求的是最坏情况下的结果。

核⼼的状态转移代码是这段:

#	当前状态为	K	个鸡蛋,⾯对	N	层楼
#	返回这个状态下的最优结果
def dp(K,	N):
	for 1 <= i <= N:
	#	最坏情况下的最少扔鸡蛋次数
			res	= min(res,	
						max(	
							dp(K - 1,i - 1),	#	碎
							dp(K, N - i)#	没碎
							) + 1 #	在第	i	楼扔了⼀次
					)
return	res

回顾这两个 dp函数的曲线, 我们要找的最低点其实就是这种情况:

for (int i = 1; i <= N; i++) {
	if (dp(K - 1, i - 1) == dp(K, N - i))
return dp(K, N - i);
}

重新定义状态转移

再回顾⼀下我们之前定义的 dp 数组含义:

def dp(k, n) -> int
# 当前状态为 k 个鸡蛋, ⾯对 n 层楼
# 返回这个状态下最少的扔鸡蛋次数

⽤ dp 数组表⽰的话也是⼀样的:

dp[k][n] = m
# 当前状态为 k 个鸡蛋, ⾯对 n 层楼
# 这个状态下最少的扔鸡蛋次数为 m

按照这个定义, 就是确定当前的鸡蛋个数和⾯对的楼层数, 就知道最⼩扔鸡蛋次数。 最终我们想要的答案就是 dp(K, N) 的结果。

这种思路下, 肯定要穷举所有可能的扔法的, ⽤⼆分搜索优化也只是做了「剪枝」 , 减⼩了搜索空间, 但本质思路没有变, 还是穷举

现在, 我们稍微修改 dp 数组的定义, 确定当前的鸡蛋个数和最多允许的扔鸡蛋次数, 就知道能够确定 F 的最⾼楼层数(相当于dp[k][m]:k是鸡蛋的个数,m是允许你扔的最大次数,结果是k和m结合可以确定的楼层高度)。 具体来说是这个意思:

dp[k][m] = n
# 当前有 k 个鸡蛋, 可以尝试扔 m 次鸡蛋
# 这个状态下, 最坏情况下最多能确切测试⼀栋 n 层的楼
# ⽐如说 dp[1][7] = 7 表⽰:
# 现在有 1 个鸡蛋, 允许你扔 7 次;
# 这个状态下最多给你 7 层楼,
# 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
# (⼀层⼀层线性探查嘛)

这其实就是我们原始思路的⼀个「反向」 版本

我们最终要求的其实是扔鸡蛋次数 m , 但是这时候 m 在状态之中⽽不是dp 数组的结果, 可以这样处理:

int superEggDrop(int K, int N) {
	int m = 0;
	while (dp[K][m] < N) {
		m++;
		// 状态转移...
	}
	return m;
}

题⽬不是给你 K 鸡蛋, N 层楼, 让你求最坏情况下最少的测试次数 m吗?

while 循环结束的条件是 dp[K][m] == N , 也就是给你 K 个鸡蛋,测试 m 次, 最坏情况下最多能测试 N 层楼。

基于下⾯两个事实:

1、 ⽆论你在哪层楼扔鸡蛋, 鸡蛋只可能摔碎或者没摔碎, 碎了的话就测楼下, 没碎的话就测楼上。

2、 ⽆论你上楼还是下楼, 总的楼层数 = 楼上的楼层数 + 楼下的楼层数 +1(当前这层楼) 。

根据这个特点, 可以写出下⾯的状态转移⽅程:

dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

dp[k][m - 1] 就是楼上的楼层数, 因为鸡蛋个数 k 不变, 也就是鸡蛋没碎, 扔鸡蛋次数 m 减⼀;

dp[k - 1][m - 1] 就是楼下的楼层数, 因为鸡蛋个数 k 减⼀, 也就是鸡蛋碎了, 同时扔鸡蛋次数 m 减⼀。

这个 m 为什么要减⼀⽽不是加⼀?

之前定义得很清楚, 这个 m 是⼀个允许的次数上界, ⽽不是扔了⼏次

在这里插入图片描述

看代码:

int superEggDrop(int K, int N) {
	// m 最多不会超过 N 次(线性扫描)
	int[][] dp = new int[K + 1][N + 1];
	// base case:
	// dp[0][..] = 0
	// dp[..][0] = 0
	// Java 默认初始化数组都为 0
	int m = 0;
	while (dp[K][m] < N) {
		m++;
		for (int k = 1; k <= K; k++)
			dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
	}
return m;
}

如果你还觉得这段代码有点难以理解, 其实它就等同于这样写:

for (int m = 1; dp[K][m] < N; m++)
	for (int k = 1; k <= K; k++)
		dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;

完整C++代码:

class Solution {
public:
    
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));//初始化为0

         /*
        //int m = 0;//初始化为0

        //每次都拿 dp[K][m] 和 N 进行比较,如果小于 N 就继续循环,如果等于 N 就说明dp[K][m]可以确定题目所给的楼层高度,直接返回
       
        while(dp[K][m] < N)
        {
            m++;
            for(int i = 1;i <= K;i++)
            {
                dp[i][m] = dp[i - 1][m - 1] + dp[i][m - 1] + 1;//加一是第i层,dp[i - 1][m - 1]是i层下面的楼层数  dp[i][m - 1]是第i层上面的楼层数
            }
        }
        */

        int m = 0;
        for(m = 0;dp[K][m] < N;)
        {
            m++;
            for(int i = 1;i <= K;i++)
            {
                dp[i][m] = dp[i - 1][m - 1] + dp[i][m - 1] + 1;
            }
        }

        return m;
    }
};

还可以再优化

再往下就要⽤⼀些数学⽅法了, 不具体展开, 就简单提⼀下思路吧

在刚才的思路之上, 注意函数 dp(m, k) 是随着 m 单增的, 因为鸡蛋个数k 不变时, 允许的测试次数越多, 可测试的楼层就越⾼

这⾥⼜可以借助⼆分搜索算法快速逼近 dp[K][m] == N 这个终⽌条件, 时间复杂度进⼀步下降为 O(KlogN), 我们可以设 g(k, m) = ……

算了算了, 打住吧。 我觉得我们能够写出 O(KNlogN) 的⼆分优化算法就⾏了, 后⾯的这些解法呢, 听个响⿎个掌就⾏了, 把欲望限制在能⼒的范围之内才能拥有快乐!

不过可以肯定的是, 根据⼆分搜索代替线性扫描 m 的取值, 代码的⼤致框架肯定是修改穷举 m 的 for 循环:

// 把线性搜索改成⼆分搜索
// for (int m = 1; dp[K][m] < N; m++)
int lo = 1, hi = N;
while (lo < hi) {
	int mid = (lo + hi) / 2;
	if (... < N) {
		lo = ...
	} else {
		hi = ...
	}
	for (int k = 1; k <= K; k++)
		// 状态转移⽅程
}

简单总结⼀下吧,

第⼀个⼆分优化是利⽤了 dp 函数的单调性, ⽤⼆分查找技巧快速搜索答案

第⼆种优化是巧妙地修改了状态转移⽅程, 简化了求解了流程, 但相应的, 解题逻辑⽐较难以想到

后续还可以⽤⼀些数学⽅法和⼆分搜索进⼀步优化第⼆种解法, 不过看了看镜⼦中的发量, 算了………… _ 

0

评论区