鸡蛋掉落

为什么直接以楼层和鸡蛋数做状态很难写？

• 问题: k 个鸡蛋、n 层楼, 求确定临界楼层的最少测试次数 (887);
• 直接定义: dp[i][j] 表示 i 个鸡蛋测 j 层的最少次数;
• 困难: 转移需要枚举在某一层扔, 并取碎与不碎两种结果的较大值, 再对所有楼层取最小; 状态数与楼层相关且转移带 min-max;
• 出路: 交换"答案"与"状态"的角色, 用逆向定义;

逆向状态如何定义？

• 新定义: dp[i][j] 表示有 i 个鸡蛋、最多扔 j 次时, 能确定的楼层数量;
• 目标转换: 找到最小的 j, 使 dp[k][j] >= n;
• 维度: 因为答案不超过 n, 所以 j 的上界取 n;

逆向转移方程如何推导？

• 在一次测试中选定楼层 x:
  • 鸡蛋没碎: 还剩 i 个鸡蛋、j-1 次机会, 能覆盖 dp[i][j-1] 层;
  • 鸡蛋碎了: 剩 i-1 个鸡蛋、j-1 次机会, 能覆盖 dp[i-1][j-1] 层;
  • 加上被测试的这一层, 合计 dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1;
• 初值: 全部为 0;
• 终止: 当 i === k 且 dp[i][j] >= n 时返回 j;

const superEggDrop = (k, n) => {
  const dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(0));
  for (let j = 1; j <= n; j++) {
    for (let i = 1; i <= k; i++) {
      dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1;
      if (i === k && dp[i][j] >= n) return j;
    }
  }
  return n;
};

• 复杂度: 时间 O(nk), 空间 O(nk);

为什么逆向定义是可行的？

• 等价性: 正向问"最少多少次", 逆向问"这么多次最多能覆盖多少层", 两者互为反函数;
• 单调性: 次数越多能覆盖的楼层单调增加, 第一个达到 n 的次数就是最优答案;
• 好处: 转移不再需要枚举楼层, 去掉一层循环;