动态规划自上而下方法矩阵中的最小代价（python）

Question

我必须在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]

天真的版本给了我正确的答案是18->；2,1,4,1,1,3,3,2,1 但第二个给了我12分

提前感谢您的帮助：）

编辑：我将原始版本称为minimal\u trajectorry\u helper（matrix，0，0）和优化版本称为dptd\u minimal\u trajectorry\u helper（matrix，m，n，track）其中track由：track=[[-1]*5]*5

Answer 1

这里的问题是如何初始化变量轨迹。注意以下事项：

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)]

我已经用上面的代码试过了，这似乎解决了问题。你知道吗