-1

I'm using python to illustrate DP algorithm. During memoization which keeps updating the table, I found that the table was not updated correctly.

I've narrowed down to the line "dp[t_id][_p] = max(choice_1, choice_2)", and I don't see what's the problem there.

tasks = [1,2,2,3]
dp = [[0]*(p+1)]*len(tasks)
for t_id in range(len(dp)):
    for _p in range(p+1):
        choice_1 = 1
        choice_2 = 2
        print dp
        dp[t_id][_p] = max(choice_1, choice_2)
        print dp

I expect the dp table should be updated one cell at a time, whereas dp[0][0] = 2, then dp[0][1] = 2, etc. However, it's updating as dp[every_column][0] = 2. The two prints in code should showcase the issue.

screenshot

enter image description here

ZDunker
  • 437
  • 1
  • 6
  • 18

1 Answers1

2
dp = [[0]*(p+1)]*len(tasks)

This creates a list of references to the same list. Let's do a simpler example:

dp = [[0] * 5] * 5
dp[0][0] = 42
print(dp)

Output:

[[42, 0, 0, 0, 0], [42, 0, 0, 0, 0], [42, 0, 0, 0, 0], [42, 0, 0, 0, 0], [42, 0, 0, 0, 0]]

As you can see, it looks like the first element of each row is set to 42. This is because each row is the same list. Instead, you need to create several independent lists with a list comprehension or a for loop. For example:

dp = [[0] * 5 for _ in range(6)]
dp[0][0] = 42
print(dp)

Output:

[[42, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

Now only the first element of the first row is set.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
  • Thank you so much! – ZDunker Oct 15 '19 at 20:52
  • 1
    @ZDunker It's an issue with Python it's easy for beginner to "by mistake" do a shallow copy. You can see the issue by using the `===` operator which check if two objects are actually the same object (and modifying one will therefore modify the other). `dp[0] === dp[1]` will return `True` with the first example, and `False` with the corrected one, because in the first the lines are all the same objects, while in the second they are all fresh new lines. – Nonyme Oct 15 '19 at 20:55
  • 1
    @Nonyme Python doesn't have a `===` operator. I think you mean the `is` operator. – Code-Apprentice Oct 15 '19 at 21:13
  • @Code-Apprentice Thank you sir, both are good things to put on top of my head. – ZDunker Oct 15 '19 at 21:52
  • @Code-Apprentice you are absolutely correct, sorry for that mistake. – Nonyme Nov 05 '19 at 19:55