Dynamic programming Topdown approach - minimum cost in a matrix (in python)

Question

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

Answer 1

The problem here is the way that you have intialised the variable track. Observe the following:

track = [[-1]*5]*5
track[2][3]=4
print(track)

Result

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

Why has the happened? when you do [a]*n you are creating n references to the same object a. In the case of a list (which is mutable), when you change it, (e.g in the line track[m][n]=result) that change will be reflected in all of the references to that list.

How to fix it

Use a list comprehnsion instead, this will create seperate copys of the 'inner list' e.g.

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

I have tried this out with the code above, and that seems to fix the problem.