概要

\(N \times M\) のグリッド上を左上から右下まで「右」または「下」への移動のみで進むとき、通過するマスの宝石の価値の合計を最大化する問題です。

考察

この問題のポイントは、「あるマス \((i, j)\) に到達する直前の状態は、必ず『上のマス \((i-1, j)\)』か『左のマス \((i, j-1)\)』のどちらかである」という点です。

なぜ動的計画法（DP）なのか

特定のマス \((i, j)\) までの最大合計値を求めたいとき、それより前の経路がどうであれ、\((i-1, j)\) または \((i, j-1)\) までに得られる最大合計値が分かっていれば、\((i, j)\) での最大値も計算できます。 このように、大きな問題を小さな部分問題に分割し、その結果を再利用する手法である「動的計画法（DP）」が最適です。

もし再帰（深さ優先探索など）で愚直に全経路を調べようとすると、経路の数は膨大な数（最大で \({}_{N+M-2}C_{N-1}\) 通り）になり、制限時間内に終わりません。DPを使うことで、各マスを1回ずつ計算するだけで済むようになります。

アルゴリズム

動的計画法の定義

\(dp[i][j]\) を「マス \((i, j)\) に到達したときの宝石の価値の最大合計値」と定義します。

遷移式

マス \((i, j)\) に来る方法は「上から」か「左から」の2通りです。よって、以下の式で更新できます。 - \(dp[i][j] = A_{i,j} + \max(dp[i-1][j], dp[i][j-1])\)

ただし、端のマスについては例外があります。 - スタート地点: \(dp[1][1] = A_{1,1}\) - 1行目: 左からしか来られないため、\(dp[1][j] = dp[1][j-1] + A_{1,j}\) - 1列目: 上からしか来られないため、\(dp[i][1] = dp[i-1][1] + A_{i,1}\)

空間計算量の最適化

通常、DPテーブルは \(N \times M\) の2次元配列で管理しますが、現在の行の計算には「一つ上の行」と「現在の行の左のマス」の情報しか使いません。そのため、1次元配列（サイズ \(M\)）を再利用して更新していくことで、メモリ使用量を節約できます。

計算量

• 時間計算量: \(O(N \times M)\)
  • グリッドの全マス（\(N \times M\) 個）を1回ずつ走査するため、計算量はマス目の数に比例します。
• 空間計算量: \(O(M)\)
  • 1次元配列でDPを管理する場合、列数 \(M\) 分のメモリのみを使用します。

実装のポイント

• 高速な入力処理: \(N, M\) が最大 1000 で、要素数が \(10^6\) 個に達するため、Pythonでは sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• 1次元DPの更新:

  • dp[j] を更新する際、更新前の dp[j] は「上のマスの値」、更新済みの dp[j-1] は「左のマスの値」を表します。これを利用して dp[j] = val + max(dp[j], dp[j-1]) と簡潔に記述できます。

• 初期化: 1行目だけは「左から足し続ける」しかないため、ループの外で個別に処理しておくと、2行目以降のメインループがシンプルになります。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白で分割して整数のイテレータを作成
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = map(int, input_data)
    
    # グリッドのサイズを取得
    try:
        N = next(it)
        M = next(it)
    except StopIteration:
        return
    
    # dp[j] は現在の行の j 列目に到達したときの宝石の価値の最大合計値を保持する
    dp = [0] * M
    
    # 1行目の初期化（右方向にのみ移動可能）
    current_sum = 0
    for j in range(M):
        current_sum += next(it)
        dp[j] = current_sum
        
    # 2行目以降の更新
    for _ in range(1, N):
        # 各行の最初の列（上からのみ移動可能）
        dp[0] += next(it)
        # その他の列（上または左から移動可能）
        for j in range(1, M):
            val = next(it)
            # dp[j-1] は左のマス(i, j-1)からの最大値、dp[j] は上のマス(i-1, j)からの最大値
            if dp[j-1] > dp[j]:
                dp[j] = dp[j-1] + val
            else:
                dp[j] = dp[j] + val
                
    # 右下のマス (N, M) に到達したときの最大値を出力
    print(dp[M-1])

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。