I have a question for Python code.

I'm trying to solve the dynamic programming LCS problem, but the Array output keeps getting weird. The code is as follows

A = "ABCBDAB"
B = "BDCABA"

lcsarray =  [[0]*(len(B)+1)]*(len(A)+1)
def lcs(x,y):
    for i in range (1,len(x)+1):
        for k in range(1,len(y)+1):
            if x[i-1]==y[k-1]:
                lcsarray[i][k] = lcsarray[i-1][k-1]+1
            else:
                lcsarray[i][k] = max(lcsarray[i-1][k],lcsarray[i][k-1])

for i in lcsarray:
    print(i)
print()

lcs(A,B)


print()
for i in lcsarray:
    print(i)

Here's the result The first line is for loop, but why does it come out like that?

python dynamic

2022-09-21 10:04

1 Answers

Replace lcsarray=[0]*(len(B)+1)]*(len(A)+1) with lcsarray=[0]*(len(B)+1) for _in range(len(A)+1)].
The first is that [0] * (len(B)+1) was copied equally in list.
That is, the same object from the first lcsarray[0] to lcsarray[len(A)]. So if you modify lcsarray[0], the rest of lcsarray[1] ~ lcsarray[len(A)] will change the same.
It's better not to do the same programming as the first one.
Moreover, if you check the object id, it will be the same.

aa = [[0] * 3] * 4
for a in aa:
    print(id(a)) # Same id

aa[0][1] = 99
for a in aa:
    print(a)

bb = [[0] * 3 for _ in range(4)]
for b in bb:
    print(id(b)) # Another id

To learn more, study aliasing, shallow copy, and deep copy.

2022-09-21 10:04

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656