887 - Hard - Super Egg Drop

LeetCode

dp(K, N): The minimum number of steps of f

Base case:

1. K = 1, we need to start from the first floor to the N-th floor, hence f is N；
2. N = 1, f is always 1;
3. N = 0, we’ve already found the floor so f is 0.

At this point, drop the egg on the floor x. The state could then be transferred to:

1. The egg is broken: dp(K - 1, x);
2. The egg is not broken: dp(K, N - x).

dp(K, N) = 1 + Max(dp(K - 1, x), dp(K - 1, N - x))

We need to find the x that makes the value smallest.

dp(K - 1, x) is increasing on x

dp(K - 1, N - x) is decreasing on x

We can binary search to find the x:

1. If dp(K - 1, x) > dp(K - 1, N - x): the x is too big;
2. If dp(K - 1, x) < dp(K - 1, N - x): the x is too small.

x should be an interger, so we need to check both the lower and higer bounds to find the smaller value.

TypeScript solution:

function superEggDrop(k: number, n: number): number {
  const dp = Array.from({ length: k + 1 }, () => Array.from<number>({ length: n + 1 }).fill(-1))

  for (let i = 1; i <= n; i++) {
    // k === 1
    dp[1][i] = i
  }

  for (let i = 1; i <= k; i++) {
    // n === 0
    dp[i][0] = 0
    // n === 1
    dp[i][1] = 1
  }

  return _find(k, n)

  function _find(_k: number, _n: number): number {
    if (dp[_k][_n] >= 0) {
      return dp[_k][_n]
    }

    let low = 1
    let high = _n
    while (low + 1 < high) {
      const x = Math.floor((low + high) / 2)
      // broken
      const f1 = _find(_k - 1, x - 1)
      // not broken
      const f2 = _find(_k, _n - x)
      if (f1 < f2) {
        low = x
      } else if (f1 > f2) {
        high = x
      } else {
        low = x
        high = x
      }
    }

    dp[_k][_n] = 1 + Math.min(
      Math.max(
        _find(_k - 1, low - 1),
        _find(_k, _n - low)
      ),
      Math.max(
        _find(_k - 1, high - 1),
        _find(_k, _n - high)
      ),
    )

    return dp[_k][_n]
  }
}