Egg Dropping Puzzle in Java

扔鸡蛋问题是一个著名的数学问题，它说明了动态规划如何能够显著减少计算时间。这个问题是在给定鸡蛋数量和楼层数的情况下，找出需要扔多少次鸡蛋才能确定鸡蛋不会摔碎的最高楼层。

问题陈述

假设你有一个

• n 层楼的建筑物。
• k 个鸡蛋用于测试。

核心问题是尽量减少找到鸡蛋不会摔碎的最高安全楼层所需的尝试次数。如果我们某个楼层摔碎了鸡蛋，那么它在所有更高楼层都会摔碎，而如果它在较低楼层没有摔碎，那么在它之下所有楼层都不会摔碎。

问题解决方案

解决方案结合了

• 递归思维：为了考虑到这一点，我们从每一层扔鸡蛋。
• 动态规划：但我们会存储中间结果，以避免重复进行相同的迭代。

动态规划解决方案

这个问题中的所有工作都可以通过动态规划高效地完成，避免了重复计算。因此，我们初始化 dp[k][n]，其中 dp[i][j] 表示使用 i 个鸡蛋和 j 个楼层的最小尝试次数。它涉及以下步骤：

初始化

• 一个鸡蛋：dp[1][j] = j 对所有 j，理由相同，你只能按顺序检查楼层。
• 我们的 dp[i][1] = 1 对所有 i，因为只有一个楼层的情况只需要一次投掷。

填充 DP 表

递归关系应该用 2 到 k 的鸡蛋数量和 2 到 n 的楼层数量来填充 dp[i][j]。

二分查找优化

与其线性测试所有楼层，不如对尝试次数进行 二分 查找。这可以将复杂度从 O(n^2) 降低到 O(n log n)。

让我们在 Java 程序中实现上述方法。

文件名：EggDropping.java

输出

 
Minimum number of attempts in worst case: 4   

解释

初始化基本情况

• dp[i][1] = 1 对每个鸡蛋 i，因为在单层楼上只需要一次尝试。
• dp[1][j] = j，因为只有一个鸡蛋时，我们必须尝试每一层。

使用二分查找填充 DP 表

• 我们迭代每个鸡蛋数量（从 2 到 k，含）和楼层数量（从 2 到 n，含）。
• 然后，我们通过二分查找来调整从中间楼层投掷的最佳情况下的 low 和 high 值。
• 为了减少尝试次数，我们计算并保存 dp[i][j] 中的值，因为我们不会进行冗余计算。

二分查找优化

• 我们使用二分查找，因此找到最佳楼层的复杂度为 O(kn log n)。

复杂度分析

时间复杂度：远比直接方法高效，由于二分查找，时间复杂度为 O(kn log n)。

空间复杂度：确实如此，因为我们存储了每个鸡蛋和楼层组合的结果，即 O(kn)。

结论

扔鸡蛋问题是动态规划如何大幅降低问题复杂性的绝佳示例。该解决方案已优化，通过递归思维和记忆化、动态规划的结合，获得了高效的计算结果。

在这种特定情况下，此解决方案可以进一步适应更复杂的情况，更多的楼层和更多的鸡蛋，验证了动态规划技术在Java中的灵活性。