LeetCode 鸡蛋掉落题解

LeetCode 鸡蛋掉落题解题目描述有 k 只鸡蛋和一栋 n 层楼找到能够确定鸡蛋最高掉落楼层的最少尝试次数。示例输入k 2,n 100输出14解题思路方法动态规划 二分查找思路使用动态规划dp[k][n] 表示 k 只鸡蛋和 n 层楼的最少尝试次数。dp[k][n] min(max(dp[k-1][i-1], dp[k][n-i]) 1) for i in 1..n。复杂度分析时间复杂度O(k * n * log n)。空间复杂度O(k * n)。代码实现def super_egg_drop(k, n): dp [[0] * (n 1) for _ in range(k 1)] for i in range(1, k 1): for j in range(1, n 1): if i 1: dp[i][j] j else: low, high 1, j while low high: mid (low high) // 2 if dp[i-1][mid-1] dp[i][j-mid]: low mid 1 else: high mid dp[i][j] 1 max(dp[i-1][low-1], dp[i][j-low]) return dp[k][n] # 测试 def test_super_egg_drop(): k, n 2, 100 print(super_egg_drop(k, n)) # 输出14 if __name__ __main__: test_super_egg_drop()总结鸡蛋掉落是动态规划和二分查找的典型应用通过二分查找优化搜索范围。