Day 004-Q3 | DP基礎（2次元）

問題

H行W列のグリッド。各セルには整数スコア。左上 (0,0) から右下 (H-1, W-1) まで右または下のみ移動するとき、通過するマスのスコアの合計の最大値を求めよ。

入力形式

H W
grid[0][0] ... grid[0][W-1]
...
grid[H-1][0] ... grid[H-1][W-1]

制約

$1 \le H, W \le 100$

$-1000 \le grid[r][c] \le 1000$

入出力例

入力例 1

出力例 1

入力例 2

2 3
-1 -2 -3
-4 -5 1

出力例 2

-5

ヒント (段階的開示)

ヒント1: 方向性

「右か下のみ」→ 2次元DP。マス (r, c) への到達方法は「上から」か「左から」のみ。

ヒント2: アプローチ

dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + grid[r][c]。境界処理に注意。

ヒント3: 誘導

dp[0][0] = grid[0][0]
for c in range(1, W):
    dp[0][c] = dp[0][c-1] + grid[0][c]
for r in range(1, H):
    dp[r][0] = dp[r-1][0] + grid[r][0]
for r in range(1, H):
    for c in range(1, W):
        dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + grid[r][c]

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(H)]

    NEG_INF = float('-inf')
    dp = [[NEG_INF] * W for _ in range(H)]
    dp[0][0] = grid[0][0]

    for c in range(1, W):
        dp[0][c] = dp[0][c-1] + grid[0][c]

    for r in range(1, H):
        dp[r][0] = dp[r-1][0] + grid[r][0]

    for r in range(1, H):
        for c in range(1, W):
            dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + grid[r][c]

    print(dp[H-1][W-1])

solve()

Step-by-Step 解説

1状態の定義
dp[r][c] = (0,0) から (r,c) まで移動したときの最大スコア。

2遷移式
マス (r,c) には「上から」or「左から」しか来られない → max(dp[r-1][c], dp[r][c-1]) + grid[r][c]。

3境界条件
最上行は左からのみ、最左列は上からのみ。-inf で初期化して「未到達」を表現。

よくあるミス

ミス	原因	正しい書き方
dp を 0 で初期化	負スコアで誤答	`-inf` で初期化
境界条件を忘れる	範囲外アクセス	最上行・最左列を別途処理
`+ grid[r][c]` 忘れ	現在マス足し忘れ	遷移式を確認

Day 004-Q3 — DP基礎（2次元）

問題