Pythonでコインマトリックスから収集できる最大コイン数を求めるプログラム

問題の概要

各セル matrix[r, c] にコインが置かれている 2 次元マトリックスを考えます。あるセル matrix[r, c] のコインを回収すると、上下の行（r - 1 行目と r + 1 行目）にあるすべてのコイン、さらに左右に隣接するセル matrix[r, c + 1] と matrix[r, c - 1] のコインが消えてしまいます。この制約のもとで、回収できるコインの合計の最大値を求めるのが目的です。

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

この場合の出力は 26 になります。8・6・9・3 のコインが置かれたセルを選べば、合計が 26 となるためです。

解法のアプローチ

この問題は、いわゆる「家を襲う（House Robber）」型の動的計画法を 2 段階に分けて適用することで効率的に解けます。

• 行単位の処理： 同じ行内では、あるセルを選ぶと左右隣のセルが利用できなくなるため、「隣接する要素を同時に選ばない」という制約下での最大和を、各行について個別に求めます。
• 行間の処理： ある行のセルを選ぶと上下の行がすべて消えるため、行ごとの結果に対して再び同じ動的計画法を適用し、マトリックス全体の最大値を導きます。

アルゴリズムの手順

1. 関数 getmax(arr) を定義します。「隣接要素を同時に選ばない」条件下での最大和を返す関数です。
2. prev_max := 0、curr_max := 0、res := 0 で初期化します。
3. arr 内の各 num について、次の処理を繰り返します。
   • temp := curr_max
   • curr_max := num + prev_max
   • prev_max := max(temp, prev_max)
   • res := max(res, curr_max)
4. res を返します。
5. メインの solve() では、以下の手順を実行します。
6. matrix が空の場合は 0 を返します。
7. m := 行数、n := 列数を取得します。
8. サイズ m の配列 row_sum を 0 で初期化します。
9. i = 0 ～ m - 1 の範囲で、row_sum[i] := getmax(matrix[i]) を計算します。
10. 最後に getmax(row_sum) を返します。

Python 実装例

理解を深めるために、以下の実装例を見てみましょう。

def getmax(arr):
    prev_max, curr_max = 0, 0
    res = 0
    for num in arr:
        temp = curr_max
        curr_max = num + prev_max
        prev_max = max(temp, prev_max)
        res = max(res, curr_max)
    return res

def solve(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    row_sum = [0 for _ in range(m)]
    for i in range(m):
        row_sum[i] = getmax(matrix[i])
    return getmax(row_sum)

matrix = [
    [2, 8, 7, 6],
    [10, 10, 4, 2],
    [5, 9, 2, 3]
]
print(solve(matrix))

入力

[
[2, 8, 7, 6],
[10, 10, 4, 2],
[5, 9, 2, 3]
]

出力

26

計算量

時間計算量は O(m × n)、空間計算量は O(m) です。各行を一度ずつ走査した後、行ごとの結果に対して一度だけ動的計画法を適用するだけでよいため、大規模なマトリックスにも対応できる非常に効率的な解法といえます。