<p>You are given <code>k</code> identical eggs and you have access to a building with <code>n</code> floors labeled from <code>1</code> to <code>n</code>.</p>

<p>You know that there exists a floor <code>f</code> where <code>0 &lt;= f &lt;= n</code> such that any egg dropped at a floor <strong>higher</strong> than <code>f</code> will <strong>break</strong>, and any egg dropped <strong>at or below</strong> floor <code>f</code> will <strong>not break</strong>.</p>

<p>Each move, you may take an unbroken egg and drop it from any floor <code>x</code> (where <code>1 &lt;= x &lt;= n</code>). If the egg breaks, you can no longer use it. However, if the egg does not break, you may <strong>reuse</strong> it in future moves.</p>

<p>Return <em>the <strong>minimum number of moves</strong> that you need to determine <strong>with certainty</strong> what the value of </em><code>f</code> is.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> k = 1, n = 2
<strong>Output:</strong> 2
<strong>Explanation: </strong>
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 2, n = 6
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> k = 3, n = 14
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= 100</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        
        
        
        
        
        # public solution ... 112 ms ... 改为一维 DP 可优化至 30 ms ...
        '''
        dp表示能达到的楼层
        最坏情况是N次，不可能超过N次
        所以从1到N+1遍历
        这种从1到N+1遍历还可以进一步优化为二分查找
        '''
        # dp = [[0]*(K+1) for _ in range(N+1)]  # dp[i][j]表示在第i次操作时，用 j 个鸡蛋可达到的最高层数
        # for i in range(1, N + 1):
        #     for j in range(1, K + 1):
        #         dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1  # 破了是dp[j-1]没破是dp[j]
        #         if dp[i][j] >= N:
        #             return i
        
        
        
        
        
        
        # my solution following public discussion ... 724 ms ... 28 % ... 19.2 MB ... 100 %
        """
        本题所求为【给定上下界，不论 F 真实取值，找出 F 所需的最小出手次数】，也即【遍历所有可能 F，计算当前 F 对应的最小次数，最后取 max 返回】
        max(min_step(F) for any F) <==> min(max_step(F) for any F)：如下述 brutal method 行所示，效率很低，需优化如下：
        
        func(lower, m, count-1) 是 m 的增函数
        func(m, upper, count)   是 m 的减函数
        而 cur 是对两者取 max，因此对于较小的 m，cur 取决于后者，对于较大的 m，cur取决于前者。
        所以 cur 是 V 字形函数曲线，而 V 的底部就是所求的 min(max_step(F) for any F) 位置
        可用二分查找搜寻 V 的底部位置
        """
        
        seen = {}
        def func(lower, upper, count):  # lower 肯定不碎，upper 肯定碎
            if lower + 1 == upper:
                return 0
            if count == 1:
                return upper - lower - 1
            
            if (upper-lower, count) not in seen:
                
                # res = float('inf')    # --> brutal method
                # for m in range(lower+1, upper):
                #     cur = 1 + max(func(lower, m, count-1), func(m, upper, count))
                #     res = min(res, cur)
                
                s, e = lower + 1, upper  # 用二分法查找第一个可摔碎的层
                while s + 1 < e:  # 下界不一定仅位于一个 m 处【可能同时存在 2 个 m 满足下界】，因此需【放宽】二分搜索终止条件
                    m = (s + e) // 2
                    broken = func(lower, m, count-1)
                    not_broken = func(m, upper, count)
                    if broken < not_broken:
                        s = m
                    elif broken > not_broken:
                        e = m
                    else:
                        s, e = m, m
                
                # s, e = lower + 1, upper  # 二分法经典写法【功能同上，但是时间从 750 ms -> 2600 ms ... 不知为啥】
                # while s < e:
                #     m = (s + e) // 2
                #     broken = func(lower, m, count-1)
                #     not_broken = func(m, upper, count)
                #     if broken < not_broken:
                #         s = m + 1
                #     else:
                #         e = m
                
                res = 1 + max(func(lower, s, count-1), func(s, upper, count))
                
                seen[upper-lower, count] = res
            return seen[upper-lower, count]
        
        return func(0, N+1, K)
        
        
        
        
        
        
23539