Pythonでグリッド上に集められるコインの最大数を求めるプログラム

問題の概要

各セルにコインが置かれた2次元行列（マトリックス）があるとします。左上の [0,0] の位置からスタートし、右または下にのみ移動できるという制約のもとで、右下隅まで移動する過程で収集できるコインの最大数を求めるのがこの問題です。

例として、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は 14 になります。これは、パス [1, 4, 2, 2, 5] を通ることで、合計14枚のコインを集められるためです。

解き方（動的計画法）

この問題は動的計画法（DP）を使うと効率的に解けます。考え方はシンプルで、「あるセルに到達した時点でのコインの最大累積数」は、「そのセル自身のコイン」と「上から来た場合・左から来た場合のうち大きい方」を足したものになります。

具体的には、入力行列 A をそのままDPテーブルとして使い、以下の手順で更新していきます。

1. まず1列目を処理します。1列目は上からしか来られないため、各行について次のように累積和を求めます。
   A[r][0] := A[r][0] + A[r-1][0]

2. 次に1行目を処理します。1行目は左からしか来られないため、各列について次のように累積和を求めます。
   A[0][c] := A[0][c] + A[0][c-1]

3. 残りのすべてのセル [r][c] に対して、上のセル A[r-1][c] と左のセル A[r][c-1] のうち大きい方を現在の値に加算します。
   A[r][c] = A[r][c] + max(A[r-1][c], A[r][c-1])

4. 最後に、行列の右下隅の値を返します。これが答えとなります。

それでは、実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, A):
      # 1列目の累積和を計算
      for r in range(1, len(A)):
         A[r][0] += A[r-1][0]
      # 1行目の累積和を計算
      for c in range(1, len(A[0])):
         A[0][c] += A[0][c-1]
      # 残りのセルを更新
      for r in range(1, len(A)):
         for c in range(1, len(A[0])):
            A[r][c] += max(A[r-1][c], A[r][c-1])
      return A[-1][-1]
ob = Solution()
matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]
print(ob.solve(matrix))

入力

matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]

出力

14

計算量について

• 時間計算量： 行数を R、列数を C とすると、すべてのセルを一度ずつ処理するため O(R × C) です。

• 空間計算量： 入力行列自体をDPテーブルとして再利用しているため、追加のメモリは O(1) で済みます。

このように、動的計画法を使えば、右・下への移動制限があるグリッド上の最適パス問題を効率よく解くことができます。同様の手法は「最小パス和」や「ユニークパス」など、他のグリッド系DP問題にも応用できます。