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 --**

- LeetCode第2919题，最小+1次数使数组变漂亮
- 和为N的加法算式
- Subset Product，子集的乘积
- Subset Sum，子集和问题
- Block Voting System，集体投票系统
- Rod-Cutting Problem，切钢条问题
- Make Change Problem，找零钱问题
- Knapsack Problem，背包问题