Last Updated: 2024-03-10 01:56:44 Sunday
-- TOC --
此题是LeetCode第887题的简化版，这里直接给出算法。详细的分析，请参考LeetCode第887题，高楼扔鸡蛋的通用解法。
class Solution:
def twoEggDrop(self, n: int) -> int:
sub = [[0]*(n+1) for _ in range(2+1)]
d = 0
while sub[2][d] < n:
d += 1
for k in range(1,2+1):
sub[k][d] = sub[k-1][d-1] + sub[k][d-1] + 1
return d
import math
class Solution:
def twoEggDrop(self, n: int) -> int:
return math.ceil(math.sqrt(0.25+n*2)-0.5)
以后再贴出2个鸡蛋的情况下，这个公式的推导过程：
Given 2 eggs and a building of N floors, we need to figure out the time complexity of the best strategy that could determine the lowest egg-broken-floor. Best strategy means to achieve this goal with minimum drop number in worst case. Fortunately, there are only 2 eggs! We have an even-split-strategy with time complexity of \(O(2\sqrt N)\) in class. But the best strategy is uneven with time complexity of \(O(\sqrt{2N})\). Now, let’s proof it.
Proof:
Let \(T(N,2)\) represents the drop number with 2 eggs and a building of N floors. This function is always increasing since the higher building the more drop number. Furthermore, after we let the first egg go in \(kth\) floor, there are only 2 choices left. If the first egg broken, we have to use the last egg to test floor bottom-up from 1 to k-1 floor. Then the drop number is just k-1. If not broken, we still have 2 eggs to test the upper part of the building which is from k+1 to N floor. If the first egg is not broken, the question is reduced to \(T(N-k,2)\). We still have 2 eggs but are facing a lower building technically.
How to choose the k? The worst case minimum drop number comes with \(k-1=T(N-k,2)\). In another word, only when the drop number given the first egg broken equals the drop number given it not broken, we get the best egg-dropping strategy, which has minimum drop number with certainty. It’s the best strategy at worst case.
Suppose there are total n drops needed, and there is a distinct k in each drop, which we use \(k_i(1\le i\le n)\) to represent. Here we have:
$$k_1=T\left(N-k_1,2\right)+1$$
$$k_2=T\left(N-k_1-k_2,2\right)+1$$
$$\ldots$$
$$k_n=T\left(N-k_1-k_2-\ldots-k_n,2\right)+1$$
Since \(T(0,2)=0\),
$$\sum_{i=1}^{n}k_i=N$$
$$k_n=1$$
If the first egg broken at the 1st drop, we have to test k_1-1 floor bottom-up one by one, so,
$$k_1=n$$
If the first egg broken at the 2nd drop, we have to test k_2-1 floor bottom-up one by one, so,
$$k_2=n-1$$
and so on,
$$k_3=n-2$$
$$\ldots$$
$$k_n=1$$
Wrap all these up,
$$n+\left(n-1\right)+\left(n-2\right)+\ldots+1=N$$
$$\frac{n\cdot\left(n+1\right)}{2}=N$$
$$n^2+n-2N=0$$
Solve this quadratic function, we get:
$$n=\frac{-1\pm\sqrt{1+8N}}{2}$$
Get rid of the meaningless negative solution, we get the n and the final big-oh:
$$n=\frac{\sqrt{1+8N\ }-1}{2}=\sqrt{\frac{1}{4}+2N}-\frac{1}{2}=O\left(\sqrt{2N}\right)$$
So, the best strategy of \(T(N,2)\) in worst case has time complexity \(O(\sqrt{2N})\).
QED
本文链接：https://cs.pynote.net/ag/dp/202401155/
-- EOF --
-- MORE --