区间动态规划例题：鸡蛋掉落问题（两枚鸡蛋，特定楼层版本） 题目描述 你有一栋从第1层到第n层的建筑，以及两枚完全相同的鸡蛋。你需要确定从哪一层楼扔下鸡蛋时，鸡蛋会摔碎。如果鸡蛋从第f层或更高扔下时会碎，而从低于f层的任何楼层扔下时不会碎，那么f称为鸡蛋的“临界楼层”。你的目标是 无论f是多少（1 ≤ f ≤ n） ，都能通过最少的实验次数（即扔鸡蛋的次数）找到f。假设鸡蛋如果没碎可以继续使用，但如果碎了就不能再使用。请设计策略，计算 最坏情况下 所需的最小实验次数。 解题思路 这是一个经典的 最坏情况最小化 问题，可以通过动态规划（DP）解决。 状态定义 ：设 dp[k][m] 表示有 k 枚鸡蛋和 m 次扔鸡蛋机会时，最多能确定多少层楼的临界楼层。 目标 ：找到最小的 m ，使得 dp[2][m] ≥ n 。 状态转移 ： 在第x层扔鸡蛋： 如果鸡蛋碎了，则临界楼层在x层以下，剩余 k-1 枚鸡蛋和 m-1 次机会。 如果鸡蛋没碎，则临界楼层在x层以上，剩余 k 枚鸡蛋和 m-1 次机会。 因此， dp[k][m] = 1 + dp[k-1][m-1] + dp[k][m-1] （1表示当前测试的楼层）。 特殊处理 ： 当 k=1 时（只有一枚鸡蛋），只能从低到高逐层测试， dp[1][m] = m 。 当 m=0 时，无法测试， dp[k][0] = 0 。 逐步计算（以n=100为例） 初始化 ： dp[1][m] = m （一枚鸡蛋时，m次机会最多测m层）。 dp[k][0] = 0 。 递推计算 （两枚鸡蛋，即k=2）： m=1 ： dp[2][1] = 1 + dp[1][0] + dp[2][0] = 1 + 0 + 0 = 1 m=2 ： dp[2][2] = 1 + dp[1][1] + dp[2][1] = 1 + 1 + 1 = 3 m=3 ： dp[2][3] = 1 + dp[1][2] + dp[2][2] = 1 + 2 + 3 = 6 m=4 ： dp[2][4] = 1 + dp[1][3] + dp[2][3] = 1 + 3 + 6 = 10 继续计算： m=5 ： 1 + 4 + 10 = 15 m=6 ： 1 + 5 + 15 = 21 m=7 ： 1 + 6 + 21 = 28 m=8 ： 1 + 7 + 28 = 36 m=9 ： 1 + 8 + 36 = 45 m=10 ： 1 + 9 + 45 = 55 m=11 ： 1 + 10 + 55 = 66 m=12 ： 1 + 11 + 66 = 78 m=13 ： 1 + 12 + 78 = 91 m=14 ： 1 + 13 + 91 = 105 ≥ 100 结论 ：当n=100时，最少需要14次实验。 策略解释 第一次扔鸡蛋的楼层选择： 若第一次在x层扔： 若碎了，剩余1枚鸡蛋和13次机会，从1层到x-1层逐层测试（最多13层）。 若没碎，剩余2枚鸡蛋和13次机会，继续在更高楼层测试（最多105-1=104层）。 通过DP表反向推导，可得到具体扔鸡蛋的楼层序列。 总结 核心思想： 用DP计算给定鸡蛋数和机会数能覆盖的最大楼层数 ，而不是直接枚举所有策略。 时间复杂度：O(k·m)，其中m是答案，通常远小于n。 扩展：此方法可推广到k枚鸡蛋的情况（经典“鸡蛋掉落”问题）。