2

这就是经典的鸡蛋掉落问题。我只是不明白递归是如何在这里工作的。它如何到达每次递归发生时返回 min+1 的函数的末尾？

请注意，我对递归的概念性理解可能存在缺陷。

/* Function to get minimum number of trials needed in worst 
case with n eggs and k floors */
int eggDrop(int n, int k) 
{ 
// If there are no floors, then no trials needed. OR if there is 
// one floor, one trial needed. 
if (k == 1 || k == 0) 
    return k; 

// We need k trials for one egg and k floors 
if (n == 1) 
    return k; 

int min = INT_MAX, x, res; 

// Consider all droppings from 1st floor to kth floor and 
// return the minimum of these values plus 1. 
for (x = 1; x <= k; x++) 
{ 
    res = max(eggDrop(n-1, x-1), eggDrop(n, k-x)); 
    if (res < min) 
        min = res; 
} 

return min + 1; 
}
4

1 回答 1

0

递归有几种基本情况，when n == 1， whenk == 0和 when k == 1。

每个非基本情况调用都有相当多的递归调用。因此，例如，如果我们想调用eggDrop(2, 5)，我们将返回类似的值

min (
  // **egg breaks**  **egg doesn't break**
  max (eggDrop (1, 0), eggDrop (2, 4) ),
  max (eggDrop (1, 1), eggDrop (2, 3) ),
  max (eggDrop (1, 2), eggDrop (2, 2) ),
  max (eggDrop (1, 3), eggDrop (2, 1) ),
  max (eggDrop (1, 4), eggDrop (2, 0) ),
)

请注意，这些案例中的每一个都将我们推向其中一个基本案例。在第一列中，我们减少n了 1，在第二列中，我们减少k了x，其中x是不大于 的正整数k。而且由于每个递归调用都使我们更接近基本情况，我们最终会触底。

（您可能可以通过证明每个递归调用n + k都严格小于其父级来正式证明这一点。我不会在这里打扰；直觉应该足够了。）

这应该解释递归实际上是如何工作的。

但请注意我们进行了多少递归调用：k * (k - 1) / 2. 这意味着这个递归版本不太可能是一个非常高效的解决方案。因此，这个问题通常用动态规划技术来解决。

于 2019-07-15T19:32:59.480 回答