CODEWITHSUNDEEP
pythonalgorithm
Yong Zheng Xin
Yong Zheng Xin

Reputation: 106

Generate 2D array in different ways

This is a DP problem, which I solve using 2D array in python.

The problem is the way I generate the 2D array.

Standard solution:

def getFloor(F, c, d):
    if d == 0 or c == 0:
        return 0
    if c == 1:
        return d
    if F[c][d] == -1:
        F[c][d] = getFloor(F, c, d-1) + getFloor(F, c-1, d-1) + 1
    return F[c][d]

def getMaxFloor(c,d):
    F = [[-1] * (d + 1) for i in range(c + 1)]
    ans = getFloor(F, c, d)
    return ans

print(getMaxFloor(3,4)) #prints 14

My code:

def getFloor(F, c, d):
    if d == 0 or c == 0:
        return 0
    if c == 1:
        return d
    if F[c][d] == -1:
        F[c][d] = getFloor(F, c, d-1) + getFloor(F, c-1, d-1) + 1
    return F[c][d]

def getMaxFloor(c,d):
    F = [[-1] * (d + 1)] * (c+1)
    ans = getFloor(F, c, d)
    return ans

print(getMaxFloor(3,4)) #prints 15, instead of the correct answer 14

I check both of the arrays F when both are initialized, which returns true. What's the problem?

Upvotes: 2

Views: 100

Answers (1)

Cary Shindell
Cary Shindell

Reputation: 1386

I'm guessing the problem is that when you multiply it, you are just creating duplicates or references to the same list element. So if you change one, you change the other. Whereas if you use the for loop, it creates separate unlinked instances so that when one gets changed it does not affect the other. (You would have to do a lot of tracing back, etc. to figure out exactly why the answer is off by exactly 1.) But this is really the only difference between the codes so it must be the problem. Hope this helps.

For example:

l = [1,2,3]
a = [2]
l.append(a)
a[0] = 4
print l
>>>[1, 2, 3, [4]]

Notice that the last element in l is [4] instead of [2].

Upvotes: 4

Related Questions