-2

首先这是问题所在：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）

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

4

1 回答 1

3

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

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

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

于 2013-03-21T21:22:40.013 回答