概要

右または下にしか進めないので、各マスまでの「最大取得価値」を動的計画法（DP）で順に計算し、右下 \((N,M)\) の値を答えます。

考察

この問題は「どの経路を選ぶと合計が最大か」を問っていますが、経路は全部で \(\binom{N+M-2}{N-1}\) 通りもあり、\(N,M \le 1000\) では全列挙は不可能です（指数的に増えるため TLE）。

重要な観察は次の通りです：

• マス \((i,j)\) に到達する直前のマスは、移動制約（右・下のみ）から
  • 上：\((i-1,j)\) から下に来る
  • 左：\((i,j-1)\) から右に来る
    の 2通りしかない。
• よって「\((i,j)\) までの最大価値」は、その2つのマスまでの最大価値の大きい方に、現在マスの宝石価値 \(A_{i,j}\) を足せばよいです。

例えば \(3 \times 3\) のとき、\((2,3)\) へ行くには \((1,3)\) か \((2,2)\) からしか来られないので、 「\((2,3)\) までの最大」は「\((1,3)\) までの最大」と「\((2,2)\) までの最大」の最大を使えば決まります。

このように「大きな問題（ゴールまで）」を「小さな問題（各マスまで）」に分解できるので DP が使えます。

アルゴリズム

1. DP の定義（2次元で考える）

\(dp[i][j] =\) マス \((i,j)\) に到達したときに回収できる宝石価値の合計の最大値（\(1\)-indexed）

すると遷移は次です：

• \(dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + A_{i,j}\)

（上から来るか左から来るかの最大を取る）

2. 1次元に圧縮（メモリ削減）

\(N,M \le 1000\) なので \(dp\) を \(N \times M\) で持っても間に合いますが、よりスマートに 1行分だけ 持てます。

コードでは - dp[j] を「現在処理中の行における列 \(j\) の最大値」として使います。 - 行を上から順に処理するとき、更新前の dp[j] は「上（前の行）の値」、 更新済みの dp[j-1] は「左（同じ行のひとつ前）の値」を表します。

更新式（コードの中身）： - up = dp[j]（更新前なので上） - left = dp[j-1]（更新後なので左） - dp[j] = max(left, up) + a

境界（左端）の処理： - 列 \(1\)（コードでは j==0）では左が存在しないので、left を非常に小さい値 NEG にして「左から来る」を選べないようにします。

最終的に dp[M-1] が \((N,M)\) の答えです。

計算量

• 時間計算量: \(O(NM)\)（全マスを1回ずつ処理）
• 空間計算量: \(O(M)\)（DP 配列は横幅分のみ）

実装のポイント

• 1次元DPの更新順が重要です。左 dp[j-1] は同じ行の更新済み、上 dp[j] は更新前、という関係を利用しています。

• 入力が最大 \(10^6\) 要素になるため、sys.stdin.buffer.readline を使って高速に読みます。

• 境界処理として、左端（j==0）では left を NEG にして不正な遷移を防いでいます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    dp = [0] * M
    NEG = -10**30

    for _ in range(N):
        row = list(map(int, input().split()))
        for j, a in enumerate(row):
            left = dp[j - 1] if j > 0 else NEG
            up = dp[j]
            dp[j] = (left if left > up else up) + a

    print(dp[M - 1])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。