algorithm - 给定 C 案例和 D 允许跌落，您可以测试的最大楼层数

Question

这个问题来自“Elements of Programming Interviews”，困扰了我几天。

问题是，“给定 c 个案例和 D 个允许跌落，在最坏的情况下，您可以测试的最大楼层数是多少”？

假设如下:

1) 所有案例都具有相同的属性，如果一个案例突破了一个水平，那么所有其他案例也会如此

2) 跌落后幸存的箱子可以再次使用，但破损的箱子将被丢弃

3) 如果一个箱子在掉落时坏了，那么如果它从更高的楼层掉下来也会坏掉。如果它幸存下来，它会在更短的坠落中幸存下来。

对我来说，这个问题似乎是“广义的两个鸡蛋问题”的变体，在这个问题中您要尽量减少掉落的次数。 此问题改为在给定确定的掉落次数的情况下寻求最大化楼层数。

解中给出的递归关系如下:

F(c + 1, d) = F(c, d - 1) + 1 + F(c + 1, d - 1)

其中 F(c, d) = max # floors 我们可以测试 w/c 个案例和 d 个下降。这种递归关系让我感到困惑，尽管这本书解释说右边的术语是我们继续进行的楼层，以防在 F(c, d - 1) + 1 楼层测试时案例没有中断。我的困惑是 -什么情况下会破裂？这不会出现在递归关系中。

这个问题还提出了额外的问题——用 O(c) 空间解决同样的问题。实现上述递归关系自然会呈现为使用 2D 内存矩阵的动态规划。您将如何使用一维数组执行此操作？

Answer 1

How would you do this with 1D array?

1.将函数重写为:F(c, d) = F(c - 1, d - 1) + 1 + F(c, d - 1)

2.这样写代码:

for (i=1; i<=D; i++)
for (j=C; j>=0; j--)
  a[j] = a[j-1] + a[j] + 1

解释:

a[j](after assignment, a[j] equals F(c, d)) 
   = a[j-1](F(c-1, d-1)) + a[j](F(c, d-1)) + 1

---

My confusion is - what accounts for when case does break?

在 x 层测试一个案例:

1. 如果 case 存活下来，那么你就知道 case 永远不会在 floor [1, x+1] 破损(对应公式中的 1 + F(c + 1, d - 1))。
2. 如果 case breaks，那么你知道 case 总是在 floor [1, x] 上 break。(对应公式中的 F(c, d - 1))