C++ 鸡蛋掉落谜题

鸡蛋掉落谜题 是一个著名的问题，需要用动态规划来最优求解。下面将描述一个涉及 N=2 个鸡蛋和 K=36 层楼的著名谜题案例。

考虑这样一个场景，我们要确定一座 36 层建筑中哪些楼层可以安全地从上面扔下鸡蛋，哪些楼层会让鸡蛋落地时碎裂。我们假设以下几点：

• 掉落后幸存的鸡蛋可以再次使用。
• 破碎的鸡蛋需要被丢弃。
• 所有鸡蛋在掉落时受到的影响都相同。
• 从较高楼层掉落的鸡蛋会碎裂，因为鸡蛋在掉落时会碎裂。
• 如果一个鸡蛋能承受从某一层楼掉落而幸存，那么它也能承受从较低楼层掉落而幸存。
• 我们不能排除鸡蛋在第一层窗户就破碎的可能性，也不能排除鸡蛋在第 36 层楼不破碎的可能性。

如果只有一个鸡蛋，并且我们希望确保得到期望的结果，那么只有一种实验方法：先从第一层楼窗户扔下鸡蛋，如果幸存，则从第二层楼窗户扔下。以此类推，一层一层往上，直到鸡蛋碎裂。在最坏的情况下，这种方法可能需要 36 次掉落。

我们要解决的问题不是找出那个关键的楼层，而是决定应该从哪些楼层扔下鸡蛋，以最大程度地减少总尝试次数。在这篇文章中，我们将讨论解决“N”个鸡蛋和“K”层楼这一问题的通用方法。

方法 1：使用递归解决鸡蛋掉落谜题

• 尝试从每一层楼（从 1 到 K）扔下一个鸡蛋，以找出在最坏情况下所需的最小掉落次数。在最坏情况下提供最小值的楼层将是解决方案的一个组成部分。
• 以下解决方案返回最坏情况下的最小尝试次数，并且这些解决方案也可以修改为输出尝试的楼层编号。

什么是“最坏情况”？

在最坏情况下，用户可以确定地处于阈值楼层。例如，如果我们有“1”个鸡蛋和“K”层楼，我们将从第一层开始扔鸡蛋，直到它碎裂，假设它在“K层”碎裂。因此，为了让我们有确定的结果，需要“K”次尝试。

最优子结构

当我们从第 x 层楼扔下鸡蛋时，可能出现两种情况：（1）鸡蛋碎裂（2）鸡蛋没有碎裂。

1. 由于在鸡蛋从“x层”掉落碎裂之前，应该存在 x-1 层楼，鸡蛋不会碎裂，因此我们需要用剩余的鸡蛋检查“x”以下的楼层。因此，问题就简化为 x-1 层楼和 n-1 个鸡蛋。
2. 如果鸡蛋从“x层”掉落后没有碎裂，则问题简化为“k-x”层楼和 n 个鸡蛋，在这种情况下，我们需要检查“x”以上的楼层。尝试从每一层楼（从 1 到 K）扔下一个鸡蛋，以找出在最坏情况下所需的最小掉落次数。在最坏情况下提供最小值的楼层将是解决方案的一个组成部分。

我们只考虑最多两种情况，因为我们需要在最坏情况下减少尝试次数。对于每一层楼，我们都会考虑上述两种情况的最大值，并选择能够导致最少尝试次数的楼层。

示例

让我们用一个例子来说明如何使用递归在 C++ 中解决鸡蛋掉落谜题。

输出

复杂度分析

时间复杂度：此程序的复杂度是指数级的，因为存在重叠子问题。

辅助空间：空间复杂度为 O(1)，因为没有使用数据结构来存储值。

方法 2：使用动态规划解决鸡蛋掉落谜题

这个问题具有重叠子问题的特性，因为子问题被反复调用。因此，鸡蛋掉落谜题同时具有动态规划问题的特征。通过自底向上构建一个临时数组 eggFloor[][]，可以避免与其他常见的动态规划 (DP) 问题相同的重计算。

形式上，对于完成 DP[i][j] 状态，其中'i'是鸡蛋的数量，'j'是楼层的数量

对于每一层楼 'x'，我们必须从 '1' 到 'j' 进行尝试，并找出至少

示例

让我们用另一个例子来说明如何使用动态规划在 C++ 中解决鸡蛋掉落谜题。

输出

复杂度分析

时间复杂度：时间复杂度为O(N * K^2)。因为我们对每个鸡蛋使用嵌套 for 循环，执行 'k^2' 次。

辅助空间：时间复杂度为O(N * K)。使用一个大小为 n*k 的二维数组来存储元素。

方法 3：使用记忆化搜索解决鸡蛋掉落谜题

在第一个递归方法中，我们可以使用一个二维dp 表来记录重叠子问题的结果，这将有助于将时间复杂度从指数级降低到二次方。

dp 表状态 -> dp[i][j]，其中 'i' 表示鸡蛋的数量，'j' 表示楼层的数量

按照以下步骤解决问题

• 创建一个大小为N+1 * K+1的二维数组 memo，然后调用 solveEggDrop(N, K) 函数。
• 如果 memo[N][K] 已经被计算过，则返回 memo[n][k]。
• 如果 K == 1 或 K == 0（基本情况），则返回 K。
• 如果 N 等于 1（基本情况），则返回 K。
• 创建一个整数res和一个整数 min，它们都等于整数最大值。
• 从 x 等于 1 开始，直到 x 小于或等于 K，运行一个 for 循环。
  • 将 res 设置为 solveEggDrop(N-1, x-1) 或 solveEggDrop(N, k-x) 的最大值。
  • 如果 res 小于整数 min，则将 min 设置为 res。
• 将 memo[N][K] 设置为 min + 1。
• 返回 min + 1。

示例

让我们用另一个例子来说明如何使用记忆化搜索在 C++ 中解决鸡蛋掉落谜题。

输出

复杂度分析

时间复杂度：O(n*k*k)，其中 n 是鸡蛋的数量，k 是楼层的数量。

辅助空间：O(n*k)，因为使用了二维记忆化表。

方法：4

按照以下概念解决问题

前面已经提到了如何使用复杂度为 O(N * K^2) 的方法，其中 dp[N][K] = 1 + max(dp[N - 1][i - 1], dp[N][K - i])，其中 i 从 1 到 K。我们已经详细研究了该方法中的所有选项。

dp[m][x] 表示使用 x 个鸡蛋和 m 次移动可以检查的最大楼层数。

按照以下步骤解决问题

• 声明一个大小为 K+1 * N+1 的二维数组和一个整数 m，其初始值为零。
• 当 dp[m][n] < k 时
  • 将 'm' 增加 1，并从 x 等于 1 开始，直到 x 小于或等于 n，运行一个 for 循环。
  • 将 dp[m][x] 设置为 1 + dp[m-1][x-1] + dp[m-1][x]。
• 返回 m。

示例

让我们用另一个例子来说明如何在 C++ 中解决鸡蛋掉落谜题。

输出

复杂度分析

时间复杂度：时间复杂度为 O(N * K)。

辅助空间：空间复杂度为 O(N * K)。

方法 5：使用空间优化 DP 解决鸡蛋掉落谜题

在此方法中，可以将该方法优化到一维 DP，因为我们只需要 DP 表的上一行数据来计算当前行，而不需要其他任何信息。

按照以下说明解决问题

• 创建一个大小为 N+1 的数组 dp 和一个整数 m。
• 从 m = 0 循环到 dp[n] k。
• 从 x 等于 n 开始，直到 x 大于零，执行嵌套 for 循环。
• 将 dp[x] 设置为 1 + dp[x-1]。
• 返回 m。

示例

让我们用另一个例子来说明如何使用空间优化 DP 在 C++ 中解决鸡蛋掉落谜题。

输出

时间复杂度：时间复杂度为 (N * log K)。

辅助空间：空间复杂度为 O(N)。