我必须在python中实现一些函数才能在矩阵中找到最小成本。我们必须向下或向右并转到相邻的数字，因此在每一步中我们只有两种可能的选择。
我写了第一个版本(天真的版本(，它有效：
def minimal_trajectorry_helper(matrix, m, n):
if ( (n > len(matrix) -1 ) or (m > len(matrix) -1)):
return 1000000000
elif ((m == len(matrix) - 1) and (n == len(matrix) - 1)):
return matrix[m][n]
else:
result = matrix[m][n] + min(minimal_trajectorry_helper(matrix, m+1, n),
minimal_trajectorry_helper(matrix, m, n+1) )
return result
但是当我想使用记忆来优化它时，我找不到正确的答案。我尝试了不同的方法，但我无法正确做到这一点。这是我写的：
def dptd_minimal_trajectorry_helper(matrix, m, n, track):
if ( (n > len(matrix) -1 ) or (m > len(matrix) -1)):
return 1000000000
elif ((m == len(matrix) - 1) and (n == len(matrix) - 1)):
return matrix[m][n]
elif (track[m][n] != -1):
return track[m][n]
else:
result = matrix[m][n] + min(dptd_minimal_trajectorry_helper(matrix, m+1, n, track),
dptd_minimal_trajectorry_helper(matrix, m, n+1, track)
track[m][n] = result
return result
这是一个例子：
[2,3,1,1,6]
[1,4,4,1,4]
[7,1,2,2,5]
[2,1,3,8,3]
[2,4,3,2,1]
天真版本给了我正确的 anwser，它是 18 -> 2,1,4,1,1,3,3,2,1但是第二个给了我 12
提前感谢您的任何帮助:)
编辑：我调用像minimal_trajectorry_helper(矩阵，0,0(这样的朴素版本和像dptd_minimal_trajectorry_helper(矩阵，m，n，轨道(这样的优化版本，其中轨道初始化为：轨道= [[-1]*5]*5
这里的问题是你初始化可变轨道的方式。请注意以下事项：
track = [[-1]*5]*5
track[2][3]=4
print(track)
结果
[-1, -1, -1, 4, -1]
[-1, -1, -1, 4, -1]
[-1, -1, -1, 4, -1]
[-1, -1, -1, 4, -1]
[-1, -1, -1, 4, -1]
为什么会这样？当您执行[a]*n时，您将创建对同一对象的 n 个引用 a 。对于列表(可变的(，当您更改它时(例如在第 track[m][n]=result 行中(，该更改将反映在该列表的所有引用中。
如何修复它
改用列表理解，这将创建"内部列表"的单独副本，例如
track = [[-1]*5 for i in range(5)]
我已经用上面的代码尝试过了，这似乎解决了这个问题。