<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:
        # dp = [[0] * (k + 1) for i in range(n + 1)]
        # for m in range(1, n + 1):
        #     for k in range(1, k + 1):
        #         dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
        #     if dp[m][k] >= n:
        #         return m
        # time: O(nk) to declare the space, O(klogn) running
        # space: O(nk)

        # dp = [0, 0]
        # m = 0
        # while dp[-1] < n:
        #     for i in range(len(dp) - 1, 0, -1):
        #         dp[i] += dp[i - 1] + 1
        #     if len(dp) < k + 1:
        #         dp.append(dp[-1])
        #     m += 1
        # return m
        # time: O(min(k, logn) ** 2)
        # space: O(min(k, logn))

        K, N = k, n
        # Right now, dp[i] represents dp(1, i)
        dp = range(N + 1)
        for k in range(2, K + 1):
            # Now, we will develop dp2[i] = dp(k, i)
            dp2 = [0]
            x = 1
            for n in range(1, N + 1):
                # Let's find dp2[n] = dp(k, n)
                # Increase our optimal x while we can make our answer better.
                # Notice max(dp[x - 1], dp2[n - x]) > max(dp[x], dp2[n - x - 1])
                # is simply max(T1(x - 1), T2(x - 1)) > max(T1(x), T2(x)).
                while x < n and max(dp[x - 1], dp2[n - x]) > max(dp[x], dp2[n - x - 1]):
                    x += 1

                # The final answer happens at this x.
                dp2.append(1 + max(dp[x - 1], dp2[n - x]))

            dp = dp2
        return dp[-1]
        # time: O(kn)
        # space: O(n)

16958