经典扔鸡蛋

/**
 * 此处存在两种变化，鸡蛋的变化（K）,楼梯数量的变化（N），那么存在两种控制变量（dp[k][n]，n 为楼梯数，而非楼层数），由谁做第一个索引，影响不大
 * 递推公式  dp[k][n]
 *   问题1： 先假设鸡蛋足够多，那么肯定是先采用二分法（中间楼层扔一个鸡蛋，由于此处存在两个变量，不能直接中间一刀切），那到底是中间哪一层呢？不妨做个假设，在楼层 j 扔下鸡蛋，则出现如下情况
 *        1. 鸡蛋碎了，则向下移动 dp[k-1][j-1]
 *        2. 鸡蛋没碎，则向上移动 dp[k][n-j]
 *    本题取的是最少次数，但是这个最小次数是保证寻找到鸡蛋不碎的楼层，所以，**此处是用 max 而非 min** ===> dp[k][n] = max(dp[k-1][j-1], dp[k][n-j]) + 1
 *
 *   问题2：得到了递推公式，那么如何求出最佳 j 呢？观察 dp[k-1][j-1], dp[k][n-j]，在 k 不变下，
 *        1. dp[k-1][j-1] 单调递增
 *        2. dp[k][n-j] 单调递减
 *   则，两个函数最小值就在  dp[k-1][j-1], dp[k][n-j] 相交处，ps 此处相交可能是个小数，那么就得判断该小数前后两个整数
 *
 *  **特殊情况**
 *  1. 鸡蛋为0：那就没必要扔了，都是 0  ===>  dp[0][ 0 ~ n ] = 0
 *  2. 鸡蛋为1：那也没必要算了，一层一层扔就行了 ===> dp[1][ 0 ~ n ] = n;
 *  3. 楼层为0：那就没必要扔了，都是 0  ===>  dp[ 0 ~ k ][ 0 ] = 0
 *  4. 楼层为1：那也没必要算了，有鸡蛋就扔一下，没有就没得扔  dp[ 0 ]][ 1 ] = 0， dp[ 1 ~ k ]][ 1 ] = 1
 *
 * 存储：由于存在两个控制变量，所以使用 **二维数组** 存储
 *
 *
 */
function superEggDrop(K: number, N: number): number {
  const dp: number[][] = [];
  for (let i = 0; i <= K; i++) {
    dp[i] = new Array(N + 1).fill(0);
  }

  // 特殊规则 1，已包含于初始化

  // 特殊规则 2
  for (let i = 1; i <= N; i++) {
    dp[1][i] = i;
  }

  // 特殊规则3，包含于初始化

  // 特殊规则4
  for (let i = 1; i <= K; i++) {
    dp[i][1] = 1;
  }

  // 开始计算咯，由于在极值情况下已单独处理，则无序考虑
  for (let egg = 2; egg <= K; egg++) {
    for (let stairs = 2; stairs <= N; stairs++) {
      // 寻找最佳的楼梯
      let left = 0,
        right = stairs;
      while (left < right - 1) {
        const middle = (left + right) >> 1;

        const middleLeftValue = dp[egg - 1][middle - 1]; // 递增
        const middleRightValue = dp[egg][stairs - middle]; // 递减

        if (middleLeftValue === middleRightValue) {
          left = right = middle;
        } else if (middleLeftValue < middleRightValue) {
          // 往右移动
          left = middle; // 为什么不想普通二分法一样，因为真正的相交点可能是小数，例如(realMiddle = 4.2, middle = 4)，如果直接 + 1 ，则超出了
        } else {
          right = middle;
        }
      }

      // 寻找到最佳扔鸡蛋楼梯后，开始扔鸡蛋，由于最佳楼梯可能为小数，所以需要判断最佳楼梯左右（left、right）

      dp[egg][stairs] =
        Math.min(
          Math.max(dp[egg - 1][left - 1], dp[egg][stairs - left]),
          Math.max(dp[egg - 1][right - 1], dp[egg][stairs - right])
        ) + 1;
    }
  }

  return dp[K][N];
}

console.log(superEggDrop(3, 14));