其中 $ 1 $ 表示当前测试的第 $ x $ 层。

区间动态规划例题：鸡蛋掉落问题（两枚鸡蛋，特定楼层版本） 题目描述 你手头有两枚完全相同的鸡蛋，需要测试它们从多少层楼高扔下会摔碎。建筑物共有 \( n \) 层（从 1 到 \( n \) 编号），你需要确定最高的安全楼层 \( f \)（即从 \( f \) 层及以下扔下鸡蛋不会碎，但从 \( f+1 \) 层及以上扔下会碎）。鸡蛋如果没碎可以重复使用，但如果碎了就不能再用来测试。目标是 在最坏情况下，最小化测试次数 （即无论 \( f \) 是多少，你的策略能保证用最少的测试次数确定 \( f \)）。 解题过程 问题分析 如果只有一枚鸡蛋，只能从 1 层开始逐层测试，最坏需 \( n \) 次。 两枚鸡蛋的优势：第一枚鸡蛋用于快速缩小范围（类似二分搜索），但如果它碎了，第二枚鸡蛋只能逐层测试剩余范围。 关键：设计策略，使得 最坏情况下的测试次数最小 。 动态状态定义 设 \( dp[ k][ m ] \) 表示有 \( k \) 枚鸡蛋，最多允许测试 \( m \) 次时，能确定的最高楼层数。 目标：找到最小的 \( m \)，使得 \( dp[ 2][ m ] \geq n \)。 状态转移： 第一次测试可以在第 \( x \) 层扔鸡蛋： 如果鸡蛋碎了，剩余 \( k-1 \) 枚鸡蛋和 \( m-1 \) 次机会，能检查 \( dp[ k-1][ m-1 ] \) 层（即 \( x \) 以下的楼层）。 如果没碎，剩余 \( k \) 枚鸡蛋和 \( m-1 \) 次机会，能检查 \( dp[ k][ m-1 ] \) 层（即 \( x \) 以上的楼层）。 因此，本次测试能覆盖的总楼层数为： \[ dp[ k][ m] = 1 + dp[ k-1][ m-1] + dp[ k][ m-1 ] \] 其中 \( 1 \) 表示当前测试的第 \( x \) 层。 初始化与递推 基础情况： 若 \( m=0 \)（无测试次数），则 \( dp[ k][ 0 ] = 0 \)。 若 \( k=1 \)（仅一枚鸡蛋），只能逐层测试，故 \( dp[ 1][ m ] = m \)。 递推：从 \( m=1 \) 开始逐步增加，计算 \( dp[ 2][ m ] \)，直到其值 \( \geq n \)。 示例计算（n=10） 初始化： \( dp[ 1][ m] = m \)，\( dp[ k][ 0 ] = 0 \)。 计算 \( m=1 \) 到 \( m=5 \) 的部分值： \( dp[ 2][ 1] = 1 + dp[ 1][ 0] + dp[ 2][ 0 ] = 1 + 0 + 0 = 1 \) \( dp[ 2][ 2] = 1 + dp[ 1][ 1] + dp[ 2][ 1 ] = 1 + 1 + 1 = 3 \) \( dp[ 2][ 3] = 1 + dp[ 1][ 2] + dp[ 2][ 2 ] = 1 + 2 + 3 = 6 \) \( dp[ 2][ 4] = 1 + dp[ 1][ 3] + dp[ 2][ 3 ] = 1 + 3 + 6 = 10 \) 当 \( m=4 \) 时，\( dp[ 2][ 4 ] = 10 \geq n \)，故最小测试次数为 4。 策略还原 通过 \( dp \) 值反向推导测试楼层： 第一次测试楼层 \( x = 1 + dp[ 1][ m-1] = 1 + dp[ 1][ 3 ] = 4 \)。 若碎，用第二枚鸡蛋从 1 层逐层测试到 3 层（最多 3 次）。 若未碎，剩余问题等价于用两枚鸡蛋测试 \( n-x=6 \) 层，需 \( m-1=3 \) 次（因为 \( dp[ 2][ 3 ]=6 \)）。 总结 本题通过定义 \( dp[ k][ m] \) 表示能力而非直接定义最小次数，简化了状态转移。核心思想是 利用鸡蛋的“韧性”在二分搜索和线性搜索间平衡 ，确保最坏情况下的效率。