动态规划问题

丢鸡蛋

有 N 层楼, 有 2 个鸡蛋, 问最坏情况下最少需要多少次扔鸡蛋, 才能确定鸡蛋不会摔碎的最高楼层? 假设 N=100.

解答
动态规划

设 dp[i][j] 表示在 i 层楼和 j 个鸡蛋的情况下，最坏情况下最少需要的扔鸡蛋次数。则状态转移方程为：

\[dp[i][j] = \min_{1 \leq x \leq i} \{1 + \max(dp[x-1][j-1], dp[i-x][j])\}\]

其中，dp[x-1][j-1] 表示在 x-1 层楼和 j-1 个鸡蛋的情况下，鸡蛋摔碎的情况；dp[i-x][j] 表示在 i-x 层楼和 j 个鸡蛋的情况下，鸡蛋没有摔碎的情况。

边界条件为：

\[dp[0][j] = 0 \quad (j \geq 1) \quad dp[i][1] = i \quad (i \geq 1)\]

最终结果为 dp[100][2]。

结果为 14, 即最坏情况下需要 14 次扔鸡蛋.