最坏情况下掉蛋

Question

我一直在尝试编写一种算法来计算在最坏情况下，即鸡蛋掉落问题中所需的最大试验次数。这是我的 python 代码

def eggDrop(n,k):
   eggFloor=[ [0 for i in range(k+1) ] ]* (n+1)
 for i in range(1, n+1):  
    eggFloor[i][1] = 1
    eggFloor[i][0] = 0
 for j in range(1, k+1):
    eggFloor[1][j] = j
 for i in range (2, n+1):
    for j in range (2, k+1):
        eggFloor[i][j] = 'infinity'
        for x in range (1, j + 1):
            res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
            if res < eggFloor[i][j]:
                eggFloor[i][j] = res

 return eggFloor[n][k]print eggDrop(2, 100)

```

代码为 2eggs 和 100floors 输出值 7，但答案应该是 14，我不知道我在代码中犯了什么错误。有什么问题？

Answer 1

问题出在这一行：

eggFloor=[ [0 for i in range(k+1) ] ]* (n+1)

您希望创建一个列表，其中包含 (n+1) 个包含 (k+1) 个零的列表。 * (n+1) 的作用略有不同 - 它创建一个列表，其中包含 same 列表的 (n+1) 个副本。

这是一个重要的区别 - 因为当您开始修改列表中的条目时 - 例如，

    eggFloor[i][1] = 1

这实际上改变了列表的所有的元素 [1]，而不仅仅是第 i 个。

要改为创建可以独立修改的单独列表，您需要如下内容：

eggFloor=[ [0 for i in range(k+1) ] for j in range(n+1) ]

通过此修改，程序 returns 14 符合预期。

（要对此进行调试，编写一个函数来弹出 eggFloor 数组并在程序的不同位置显示它可能是个好主意，这样您就可以将它与您的预期进行比较。很快就会很清楚发生了什么！）

最坏情况下掉蛋

Egg dropping in worst case

function

dynamic-programming