0

I have to implement some functions in python to find the minimum cost in a matrix.We must go down or right and to an adjacent number so at each step we have only two possible choices.

i wrote the fisrt version (naive one) which works:

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

But when i want to optimize it using memoization i can't find the right answer. I tried different ways but i wasn't able to do it correctly. Here is what i wrote:

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

Here is an example :

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

The naive version gives me the right anwser which is 18 -> 2,1,4,1,1,3,3,2,1 But the second one gives me 12

Thanks in advance for any help :)

EDIT : I call the naive version like minimal_trajectorry_helper(matrix, 0, 0) and the optimized one like dptd_minimal_trajectorry_helper(matrix, m, n, track) where track is initialized by : track = [[-1]*5]*5

4

1 回答 1

0

这里的问题是您初始化变量轨道的方式。请注意以下事项：

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。在列表（可变）的情况下，当您更改它时（例如在 line 中track[m][n]=result），该更改将反映在对该列表的所有引用中。

如何修复它

改用列表理解，这将创建“内部列表”的单独副本，例如

track = [[-1]*5 for i in range(5)]

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

于 2018-01-31T23:30:53.573 回答