Euler项目82（Python）

Question

首先这是个问题：https://projecteuler.net/problem=82。 这是我的代码：

# https://projecteuler.net/problem=82

matrice = open('matrix3.txt','r').read().split('\n')
m = []
for el in matrice:
    if el=='':
        continue
    tmp = el.split(',')
    m.append(tmp)
matrix = [[0 for i in range(80)]for j in range(80)]
x,y = 0,0
while(True):
    matrix[x][y]=int(m[x][y])
    y+=1
    if y==80:
        y=0
        x+=1
        if x==80:
            break 
tmp = [0]*80
x,y = 0,78
while(True):
    if x==0:
        tmp[x]=min(matrix[x][y+1],matrix[x+1][y]+matrix[x+1][y+1])
    if x==79:
        tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1])
    else:
        tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1],matrix[x+1][y]+matrix[x+1][y+1])
    x+=1
    if x==80:
        for e in range(80):
            matrix[e][y]+=tmp[e]
        tmp = [0]*80
        x=0
        y+=-1
        if y<0:
            break
minimo = 10**9
for e in range(80):
     if matrix[e][0]<minimo:
        minimo=matrix[e][0]
print(minimo)

此代码背后的思想是： 我从第79列开始（如果从0开始计数，则是第78列），然后计算从该列中的任何给定项到右侧列的最佳（最小）方法。 当列结束时，我用找到的最小结果替换它，并开始对左边的列执行相同的操作。在

有人能帮我理解为什么我会得到错误的答案吗？（我得到262716）

同样的代码也适用于示例中的矩阵（当然，如果您更改索引，它也会起作用）。在

Answer 1

如果我正确地理解了这个问题，你的代码和你的算法，看起来你实际上并没有计算出从一个列到下一个列的最佳方法，因为你只考虑了几种可能的到达下一列的方法。例如，考虑第一次迭代（when y=78）。然后我想你想要的是tmp[0]保持从matrix[0][78]到第79列中任何地方的最小和，但是你只考虑两种可能性：向右走，或者向下然后向右走。如果从matrix[0][78]到下一列的最佳方法是向下搜索6个条目，然后再向右移动呢？你的代码永远不会考虑这种可能性。在

您的代码可能适用于小示例，因为在每个列中，最小路径只上下一次。但我认为这是一个巧合（也可能是一个选择不当的例子）。在

解决这个问题的一种方法是使用以下方法。当输入是NxN矩阵时，定义NxN数组min_path。我们要填充min_path，这样min_path[x][y]是从输入矩阵第一列的任何条目开始到[x][y]的最小路径和。我们一次填充min_path的一列，从最左边的一列开始。为了计算min_path[i][j]，我们查看min_path第（j-1）列中的所有条目，以及从这些条目中获取（i，j）的成本。下面是一些Python代码显示了这个解决方案：https://gist.github.com/estark37/5216851。这是一个O（N^4）的解决方案，但它可能会更快！（可能通过预计算sum_to调用的结果？）在