【Python】二次元累積和リストを求めるプログラムを書きたい

実現したいこと

『競技プログラミングの鉄則』という本で数理アルゴリズムを勉強しています。そのなかで二次元のリストをインプットとして、それをもとに二次元の累積和リストをアウトプットとして作成するプログラムを開発しています。

前提

具体的な値を用意し、ここではインプットとなる二次元リストlstを下記の値でデバッグを行いました。後述のソースコードで用いられるHとWはそれぞれ標準入力によって得られるインプットの二次元リストの行数と列数を表す変数です。

main.py

1lst = [ 2 [2, 0, 0, 5, 1], 3 [1, 0, 3, 0, 0], 4 [0, 8, 5, 0, 2], 5 [4, 1, 0, 0, 6], 6 [0, 9, 2, 7, 0] 7 ]

該当のソースコード

lstを縦方向に累積和をとったリストlst_1を作成したのち、lst_1を横方向に累積和を取ったリストlst_2を考えました。(横方向への累積和の部分は質問から外れるため省略します)

続いて、lst_1の1行目(lst_1[0])に初期値を代入し、累積和を求めました。

main.py

1#lstの二次元累積和行列作成 2lst_1 = [[None]*W]*H #縦方向 3lst_2 = [[None]*W]*H #横方向 4 5#縦方向の累積和 6lst_1[0] = lst[0] 7for i in range(1,H): 8 for j in range(W): 9 lst_1[i][j] = lst_1[i-1][j] + lst[i][j] 10 11print(lst_1) 12 13#横方向の累積和(省略)

求めたい出力と実際の出力

縦方向の累積和の二次元リストが想定通りに求められているのであれば下記の実行結果が得られます。

#求めたい出力結果 [ [2, 0, 0, 5, 1], [3, 0, 3, 5, 1], [3, 8, 8, 5, 3], [7, 9, 8, 5, 9], [7, 18, 10, 12, 9] ]

しかし実際の実行結果は下記のようになり、初期値以外の全ての値がlst_1[4]の値となってしまいます。

#実際の出力結果 [ [2, 0, 0, 5, 1], [7, 18, 10, 12, 9], [7, 18, 10, 12, 9], [7, 18, 10, 12, 9], [7, 18, 10, 12, 9] ]

試したこと

処理中の値を確認するために内側のfor文が一旦終わったタイミングでprint(lst_1[i])を挿入し、実行結果を確認したところ、求めたい値となっているところまでは確認できました。

main.py

1#縦方向の累積和 2lst_1[0] = lst[0] 3for i in range(1,H): 4 for j in range(W): 5 lst_1[i][j] = lst_1[i-1][j] + lst[i][j] 6 print(lst_1[i]) #追加

#実行結果 [3, 0, 3, 5, 1] [3, 8, 8, 5, 3] [7, 9, 8, 5, 9] [7, 18, 10, 12, 9]

しかし、外側のfor文が終わったタイミングで出力結果を見ると、初期値以外の全ての値がlst_1[4]の値となってしまい、どこに原因があるのかわかりませんでした。

書籍に記載の回答コードを見て理解したものの、自分で考えて書いたコードのなかでどこが原因となっているのか知りたかったため、この場を借りて質問させていただきます。

よろしくお願いいたします。

環境

実行環境は下記の環境を使っています
https://atcoder.jp/contests/tessoku-book/custom_test