0

I'm working on a dynamic programming problem (longest common subsequence)

My issue: building the matrix.

I initially build my matrix with dp1. but it kept churning out the wrong answers. Then I referenced other answers and used dp2, which produces the right answer.

For example:

s1 = ELGGYJWKTDHLXJRBJLRYEJWVSUFZKYHOIKBGTVUTTOCGMLEXWDSXEBKRZTQUVCJNGKKRMUUBACVOEQKBFFYBUQEMYNENKYYGUZSP

s2 = FRVIFOVJYQLVZMFBNRUTIYFBMFFFRZVBYINXLDDSVMPWSQGJZYTKMZIPEGMVOUQBKYEWEYVOLSHCMHPAZYTENRNONTJWDANAMFRX

The right answer should be 27.

  • dp1 gives 30
  • dp2 gives 27

I'm puzzled. What's the difference? isn't "for _ in range(m+1)" essentially iterating whatever is before by m+1 times? please help me out.

def commonChild(s1, s2):
    n, m = len(s1), len(s2)
    dp1 = [[0] * (n+1)] * (m+1)
    dp2 = [[0] * (n+1) for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if s2[i] == s1[j]:
                dp[i+1][j+1] = dp[i][j] +1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    return dp[-1][-1]
Julliard
  • 523
  • 1
  • 6
  • 23

1 Answers1

2
>>> a=[[0] * (5) for i in range(4)]
>>> a
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
>>> a[0][0]=1
>>> a
[[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
>>> a=[[0] * (5) ]*4
>>> a[0][0]=1
>>> a
[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

You can see the difference yourself,

in [[0]*(n+1)]*(m+1) it is referring to the same array [0] * (n+1) so changing one array value changes the same value in all

Albin Paul
  • 3,330
  • 2
  • 14
  • 30