The problem is here:
table = [[2] * n] * n
What this does is make a list consisting of one n-element list n times. The problem is that, since these are the same (is
-same, not just ==
-same) list and not copies, they all get updated together, which is bad, e.g.,
>>> lst=[[2]]*2
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
True
>>> lst[0][0]=1
>>> lst
[[1], [1]]
The fix is to write
table = [[2] * n for i in range(n)]
which runs [2] * n
repeatedly to obtain n copies, which initially are ==
-same but not is
-same.
>>> lst=[[2]for i in range(2)]
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
False
>>> lst[0][0]=1
>>> lst
[[1], [2]]
EDIT: Also, for j in range(n - 1, -1, -1):
should be for j in range(n - 2, -1, -1):
to match the pseudocode exactly, though this is not the cause of the bug.