887. 鸡蛋掉落 [hard]
887. 鸡蛋掉落 [hard]
https://leetcode-cn.com/problems/super-egg-drop/
你将获得 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 <= K <= 100
- 1 <= N <= 10000
通过次数25,917 | 提交次数90,746
Forth Try (Time Exceeded Version)
2020-09-02
这种题目第一眼看上去几乎是无解，根本不知道在考什么，也不知道什么决策依据。
刚开始动态规划也没法一眼看出来，但知道这是动态规划题目，勉强写出了超时版本，还是没法想到摔和不摔可以根据楼层用二分法进行时间缩减, 算了算了。
不过这个动态规划写得思路就清晰多了，遍历所有楼层选择最合适次数最少的第一个楼层扔，而对于每个楼层则按照鸡蛋碎和不碎进行下一步拆分，选择其中次数最大的。
另外测试了无限鸡蛋的情况下，第一个最合适扔的楼层。从该楼层扔下之后，按照摔和不摔需要动态选择不同的路径，都汇合起来从该楼层开始摔确实需要的数量最少。
- 10层楼最少需要扔4次，第一个鸡蛋扔3楼；
eggs 100, floor N10, minimum drop is 4, first drop from 3 floor is the best
- 100层楼最少需要扔7次，第一个鸡蛋扔37楼。
eggs 100, floor N100, minimum drop is 7, first drop from 37 floor is the best
eggs 100, floor N37, minimum drop is 6, first drop from 6 floor is the best
eggs 100, floor N63, minimum drop is 6, first drop from 32 floor is the best
eggs 100, floor N6, minimum drop is 3, first drop from 3 floor is the best
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
# 每次扔下去，要么碎了减少一个鸡蛋，减少一层楼；要么没碎增加一层楼
# 目标值是在当前楼没碎，在楼上碎了，则F为当前楼
# dp[k][n] 代表需要测试多少次
# 每次总归要选择一层楼开始扔，选择其中dp最小的楼层
dp = [[""] * (N + 1) for _ in range(K + 1)]
cache_idx = dict()
# 初始化，只有一个鸡蛋的时候，n层楼就需要扔n次
for i in range(1, N + 1):
dp[1][i] = i
# 只有一层楼的时候，只需要扔1次
for i in range(1, K + 1):
dp[i][1] = 1
def dfs(k, n):
if k < 1 or n < 1:
return 0
if dp[k][n] != "":
return dp[k][n]
f_and_idx = [float('inf'), None]
# 每次总归要选择一层楼开始扔，选择其中dp最小的楼层
for i in range(1, n + 1):
# 如果没碎, 到楼上去测试
f_safe = dfs(k, n - i) + 1
# 如果碎了，到楼下去测试
f_broken = dfs(k - 1, i - 1) + 1 # 写成dfs(k - 1, n - 1) t+ 1 调试了很久。。
# 为了确定在i楼扔下的f值，需要选取最大的
f_i = max(f_safe, f_broken)
# 在所有楼层中，选择最小的扔法
f_and_idx = min(f_and_idx, [f_i, i])
dp[k][n], cache_idx[(k, n)] = f_and_idx
return dp[k][n]
rv = dfs(K, N)
print(f" eggs {K}, floor N{N}, minimum drop is {rv}, first drop from {cache_idx[(K, N)]} floor is the best")
return rv
Third Try
2020-07-04
这应该是一个更容易理解的版本，奈何我还是没看出状态方程怎么来的，这两天精神实在不好，没法想明白。
DP[k][t] = DP[k-1][t-1] + DP[k][t-1]，为什么是加，而不是求两者最小呢？
参考的题解
https://leetcode-cn.com/problems/super-egg-drop/solution/887-by-ikaruga/
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
# 把问题转变成K个鸡蛋，移动T次，能够确定多少个F, 然后-1就是N了
# DP[K][T] 问题
# DP[1][T]次，只能确定T层楼
# DP[K][1]次，只能确定1层楼
# 好像想不出状态转移方程啊
# DP[2][2], 2层楼，DP[2][3],
# DP[k][t] = DP[k-1][t-1] + DP[k][t-1] # 看题解来的，实在想不出来。。。
cache = dict()
def gocha(k, t):
if t == 1:
return 2
if k == 1:
return t + 1
return gocha(k-1, t - 1) + gocha(k, t-1)
i = 1
while gocha(K, i) - 1 < N:
i += 1
return i
- 执行用时：100 ms, 在所有 Python 提交中击败了80.63%的用户
- 内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户
Second Try
2020-07-04
真是一道浪费了无数时间的题目
能够从一个N重循环找极小的极大值函数中找到二分法的解法，是在太牛逼了。 而且学习了在不同场景的二分法查找法，比如这种low和high的写法，每次直接low = mid或者high = mid，并不需要mid +- 1，而且判断条件是while low + 1 < high, 这样终止条件就是low + 1 = high，或者当相等的时候low = high， 总归low不会大于high. 最终low和high之间只会相差最多1个数值。
- 一个痛心疾首的bug: 在二分法的时候，当left = right的时候，lo = hi = x,写成了lo = x = hi.花了很长时间都找不出来，尤其是这道题的递归调试太麻烦了。
# lo = x = hi # 傻逼啊，这个bug。。。
lo = hi = x
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
dp = [[""] * (N + 1) for _ in range(K + 1)]
for i in range(1, K+1):
dp[i][1] = 1
dp[i][0] = 0 # 如果在1楼摔了，0楼的就不用考虑了
for i in range(1, N+1):
dp[1][i] = i
def findDP(K, N):
# print(K, N, dp[K][N])
if dp[K][N] != "":
return dp[K][N]
# sep = []
# 这里把x从1到N拆开来，刚好是两个跟着x的单调递增和单调递减函数
# for x in range(1, N+1):
# f = max(findDP(K-1, x-1), findDP(K, N-x)) + 1
# sep.append(f)
# # print(sep)
# dp[K][N] = min(sep)
# 新的二分写法，直接用下边界和上边界进行替代
# 终结条件是low和hight之间间隔小于等于1，low +1 <= right，判断条件是while low + 1 < right, 间隔大于1，毕竟走完一波循环后就不是了
lo = 1
hi = N
while lo + 1 < hi:
x = (lo + hi) / 2
ls = findDP(K-1, x-1)
rs = findDP(K, N-x)
if ls < rs:
lo = x
elif ls > rs:
hi = x
elif ls == rs:
# lo = x = hi # 傻逼啊，这个bug。。。
lo = hi = x
# 得到lo和hi后，其实并不知道哪个会使得两个函数的最大值最小，于是都得试一遍，lo和hi最多只间隔一个
# print("lo", lo, "hi", hi, "k", K)
rv = 1 + min(max(findDP(K-1, lo - 1), findDP(K, N - lo)),
max(findDP(K-1, hi - 1), findDP(K, N - hi)))
# print(K, N, "rv: ", rv, "lo: ", lo, "hi: ", hi)
dp[K][N] = rv
return dp[K][N]
return findDP(K, N)
- 执行用时：488 ms, 在所有 Python 提交中击败了65.11%的用户
- 内存消耗：46 MB, 在所有 Python 提交中击败了100.00%的用户
First Try
试了几个都没问题，到100, 10000级别就开始内存超标了，应该是堆栈超出了。
dp[k][n], 在x层开始扔：
- 蛋碎: dp[k-1][x-1] (蛋减少一个，楼层往下走)
- 蛋没碎: dp[k][N - x] (蛋不变，楼层是[x+1, N-1], 总楼层数N-1-(x+1) + 1 = N - x - 1?)
- 如果要两边都覆盖，需要选择最大的一边，这样不管哪边都没压力，因此是max(dp[k-1][x-1], dp[k][N-x])
- 然后第一个可以从1到n-1各种扔，因此是min(1～n-1的x)(max(dp[k-1][x-1], dp[k][n-x]))
初始动态方程写好后，至少有解了，虽然是KNN的复杂度。
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
"""
dp[k][n], 在x层开始扔
蛋碎: dp[k-1][x-1] (蛋减少一个，楼层往下走)
蛋没碎: dp[k][N - x] (蛋不变，楼层是[x+1, N-1], 总楼层数N-1-(x+1) + 1 = N - x - 1?)
如果要两边都覆盖，需要选择最大的一边，这样不管哪边都没压力，因此是max(dp[k-1][x-1], dp[k][N-x])
然后第一个可以从1到n-1各种扔，因此是min(1～n-1的x)(max(dp[k-1][x-1], dp[k][n-x]))
本来非常头疼都是楼层的有效数量，因为0<=F<=N, 因此肯定不用从N层往下扔，肯定不会被摔破。所以需要扔的楼层是[1, N-1],总共N-1个楼层。
这样的话，dp[k][n]是个什么意思，x层不碎的话，dp[k][n-x]还是dp[k][n-x-1]，就很头疼
但是dp[k][n]不考虑这个，在计算dp[k][n]的时候本身就已经考虑到[1, N-1]的情况，不需要在dp的索引上进行处理
dp[1][1]为1, dp[1][2] = 1 这个会被承认吗？2层楼只要试一次就行了，1层楼也只需试一次. dp[1][n] = n-1 （除了n==1)
dp[2][1]为1, dp[n][1]都为1
被测试案例毒打: 1个鸡蛋2层楼的时候，还是需要扔两次。
扔1楼的时候如果没碎，也需要到2楼去确认下，需要扔2次；如果1楼碎了，那么肯定是2楼，只要扔1次。 因此两者中选最大的，需要2次。
"""
dp = [[""] * (N + 1) for _ in range(K + 1)]
for i in range(1, K+1):
dp[i][1] = 1
dp[i][0] = 0 # 如果在1楼摔了，0楼的就不用考虑了
for i in range(1, N+1):
dp[1][i] = i
def findDP(K, N):
# print(K, N, dp[K][N])
if dp[K][N] != "":
return dp[K][N]
sep = []
for x in range(1, N+1):
f = max(findDP(K-1, x-1), findDP(K, N-x)) + 1
sep.append(f)
# print(sep)
dp[K][N] = min(sep)
return dp[K][N]
return findDP(K, N)