蛋滴难题中的递归

Question

有n个鸡蛋和有k层的建筑物。写一个算法，找出最低滴数是必需的，以知道地板上，如果鸡蛋是从，它将打破。

我的解决办法是把地板分成几块大小的方形(K)。例如，如果k =100，我将检查鸡蛋是否会从第10层、第20层、第30层.100中断裂，然后在该块中进行线性搜索。解决方案是O(sqrt(k))。

现在，我看到的动态规划解决方案是：

When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials. 
     k ==> Number of floors
     n ==> Number of Eggs
      eggDrop(n, k) ==> Minimum number of trials needed to find the critical
                        floor in worst case.
      eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                     x is floors in {1, 2, ..., k}}

我不知道为什么我们要用eggDrop(n, k - x)来计算Floor above x with k-x，因为它会在x，下面给出k层，而不是在X-确切的之上的楼层？

例如，on x=6

eggDrop(10, 2) = 1 + min{max(eggDrop(2 - 1, 6 - 1), eggDrop(2, 9 - 6))

给予，

eggDrop(10, 2) = 1 + min{max(eggDrop(1, 5), eggDrop(2, 3))

eggDrop(2，3)基本上是一座有3层和2个鸡蛋的建筑，而不是6楼以上的一层。

谢谢!

来源：https://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/

Answer 1

那层楼是什么都没关系。重要的是我们需要考虑的楼层数。如果我们有9层楼，6楼有一个鸡蛋，我们需要考虑6层以上的3层:7层、8层和9层。另一种思考方法是，必须测试楼层7-9与测试楼层1-3 (在最坏情况下下降的次数)完全相同。

Answer 2

那么，六楼以上有几层楼？是3层( 7、8、9层)。如果你想找出哪一个是罪魁祸首，那么这些楼层有多高并不重要。

让我给你们画一个不同的例子，以供参考。假设您试图通过排序列表进行二进制搜索，以查看是否存在一个元素。

示例列表：values = [0, 1, 2, 3, 4]

假设您正在搜索3。第一步是查看中间元素v[2]并将其与3进行比较。由于3大于v[2] = 2，所以应该在子数组v[3 - 4]上递归调用binarySearch(a1)。

在递归调用中会发生什么？在这一点上，它基本上是一个基本案例，因此它可能会查看a1[0] = 3。比较有效，所以您可以返回TRUE。

在本例中，在子数组binarySearch上调用v[3 - 4]与调用eggDrop(2, 3)相同。当您引用a1[0]时，您实际上是在引用v[3]。类似地，递归调用eggDrop中的第1层实际上是引用父调用中的第7层。索引“重置”，但它们实际上指的是相同的值。