for文と掛け算による多次元配列の作り方

Question

前提・実現したいこと

pythonで掛け算を使って２次元元配列を作り、Exhaustive Searchのプログラム（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja）を書いたのですが、正しい結果になりません。
なぜか、for文を使って２次元配列を作ると正しい結果になります。
その理由がわからないので、どなたか教えて頂けないでしょうか。

発生している問題・エラーメッセージ

input:
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

間違ったoutput:
no
no
yes
no　
yes
yes
no
yes

該当のソースコード

from sys import stdin

input = stdin.readline

n = int(input())
A =[int(x) for x in input().split()]
q = int(input())
M =[int(x) for x in input().split()]

dp = [[None]*2001]*21

def solve(i,m):
if dp[i][m] != None:
return dp[i][m]
if m == 0:
dp[i][m] = True
elif i >= n:
dp[i][m] = False
elif solve(i+1,m):
dp[i][m] = True
elif solve(i+1,m-A[i]):
dp[i][m] = True
else:
dp[i][m] = False
return dp[i][m]

def main():
for m in M:
if solve(0,m):
print("yes")
else:
print("no")

if name == "main":
main()

試したこと

dp = [[None for _ in range(2001)] for _ in range(21)]
とすると正しい結果になります。

正しいoutput:
no
no
yes
yes
yes
yes
no
no

補足情報（FW/ツールのバージョンなど）

Python 3.7.5 (default, Oct 25 2019, 10:52:18)
[Clang 4.0.1 (tags/RELEASE_401/final)] :: Anaconda, Inc. on darwin
Type "help", "copyright", "credits" or "license" for more information.

Comments

[ozwk]

こちらの質問と原因は一緒です
https://teratail.com/questions/296284

[fxf000]

ありがとうございます！

Answer 1

[リスト]*nで作った一つ一つの要素は全部同一のオブジェクトです

x = [0,0,0]
y = [x] * 3

print(y) # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

y[0][0] = 1

print(y) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
print(x) # [1, 0, 0]

Comments

[fxf000]

すごく分かり易かったです。ありがとうございました！