ナップサック問題について

Question

現状

競技プログラミングを通して、アルゴリズムとコーディングについて勉強中です。
動的計画法の典型問題にナップサック問題（厳密に違いを分ける場合もあるらしい）について、いくつかのホームページを見て勉強しました。
動的計画法(ナップサック問題)
理解した内容をもとに、競技プログラミングの例題(Knapsack 1)に取り組んでみたのですが、回答が合わないようです。
以下は、私の書いたコードです。

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[-1]*(w+1)]*(n+1)
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])

やったこと・教えてもらいたいこと

再帰関数を用いて、別の書き方を試してみましたが答えが合いませんでした。
浅い理解、あるいはどこか本質的に間違った理解をしていることが原因だと思います。
私の書いたコードの問題点や、改善点などを教えていただけないでしょうか？

Answer 1

こう直すと通ります。

-DP=[[-1]*(w+1)]*(n+1)
+DP=[[0]*(w+1) for _ in range(n+1)]

• もとの作り方だと DP[0], DP[1], DP[2], .... に全部同じインスタンスが入っちゃうので、DP表の更新で想定しないとこまで書き換わってます。（手元で適当に a = [[0]*10]*10 みたいなのを作って a[0][0] を書き換えたりすると確認できます）
• 初期値 -1 の分だけ答えがズレてたので調整。

python3だとTLEしましたが、pypy3で通りました。

Comments

[退会済みユーザー]

解答ありがとうございます。
アルゴリズム以前に参照(?)に対する意識が足りなさ過ぎたようです。