Project 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

如果我理解你的问题、代码和算法没错的话，看起来你并没有真正计算从一列到另一列的最佳路径，因为你只考虑了几种可能的方式。例如，考虑第一次循环（当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调用的结果？）