グリッド上のUnique Pathsと最小経路和
障害物のある場合とない場合のUnique Pathsについて2D DPテーブルを埋め、経路上の値の合計を最小化する問題へ応用します。
「グリッド上のUnique Pathsと最小経路和」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
グリッド上のUnique Paths
Unique Paths（LeetCode 62）では、m×nのグリッドで、右または下にしか移動できない場合に、左上の角から右下の角まで進む異なる経路の数を求めます。3×7のグリッドでは答えは28です。重要な考え方は、セル (i,j) へのすべての経路が、(i-1,j)（上）または (i,j-1)（左）のどちらかから来るということです。これにより、自然な2次元DPの定式化が得られます。
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2Unique Paths の2次元DPテーブル
dp[i][j] をセル (i,j) までの経路数と定義します。最初の行と最初の列はすべて1です（最上行または最左列の各セルに到達する方法は1通りしかないためです）。それ以外のセルでは、dp[i][j] = dp[i-1][j] + dp[i][j-1] となります。テーブルを行ごとに埋め、答えとして dp[m-1][n-1] を求めます。時間計算量はO(m×n)、空間計算量はO(m×n)で、O(n)まで削減できます。
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)O(n)への空間最適化
dp[i][j] は現在の行と直前の行だけに依存するため、完全な2次元テーブルを1次元配列1つに置き換えられます。すべての値を1で初期化し、各行について dp[j] += dp[j-1] とインプレースで更新します。行 i の処理後、dp[j] には2次元テーブルでの dp[i][j] に相当する値が入ります。これは2次元DP問題でよく使われる最適化パターンです。
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Unique Paths II：障害物
Unique Paths II（LeetCode 63）では、グリッドに障害物（1が設定されたセル）が追加されます。障害物を通る経路は無効なので、obstacle[i][j] == 1 なら dp[i][j] = 0 です。それ以外では、漸化式は同じで dp[i][j] = dp[i-1][j] + dp[i][j-1] となります。始点または終点が塞がれている場合、答えはただちに0です。基本ケースは注意深く初期化してください。最初の行または列で1が現れたら、その行または列の後続セルはすべて0になります。
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2最小パス和問題
Minimum Path Sum（LeetCode 64）では、非負整数で満たされたm×nのグリッドが与えられ、右または下にだけ移動して左上から右下まで進む経路のうち、経路上のすべての数の合計が最小になるものを求めます。たとえば [[1,3,1],[1,5,1],[4,2,1]] では、1→3→1→1→1という経路の合計が7になります。DPの状態はUnique Pathsと同じですが、漸化式では加算ではなく最小値を使います。
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)最小パス和のDP実装
dp[i][j] をセル (i,j) に到達するための最小コストと定義します。基本ケースは dp[0][0] = grid[0][0] です。最初の行は dp[0][j] = dp[0][j-1] + grid[0][j] です（左から来る方法しかないためです）。最初の列は dp[i][0] = dp[i-1][0] + grid[i][0] です（上から来る方法しかないためです）。一般の場合は dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) となります。これは最適性原理をそのまま表したものです。
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7インプレースでの最小パス和
入力グリッドを変更してよい場合は、グリッドをインプレースで更新し、別のDPテーブルの確保を避けられます。これにより、補助領域の空間計算量をO(1)にできます（入力自体に必要な領域は除きます）。面接では、この最適化について尋ねられることがあります。実行する前に、入力の変更が許可されているか確認してください。許可されていない場合は、1次元のローリング配列を使うことで、入力を変更せずに空間計算量をO(n)にできます。
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7三角形の最小パス和
Triangle（LeetCode 120）では、三角形状の配列の最上段から最下段まで、最小パス和を求めます。各ステップでは、下の行にある隣接した数へ進みます。ボトムアップDPが最も簡潔です。最後から2番目の行から開始し、各セルに、その真下にある2つのセルのうち小さい方を加えます。これにより開始位置を追跡する必要がなくなり、答えが自然に頂点へ集約されます。
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)ダンジョンにおけるグリッドDP
Dungeon Game（LeetCode 174）では、負の値（ダメージ）と正の値（回復）を持つグリッドで、右下にいる王女を救出するために必要な初期体力の最小値を求めます。移動できる方向は右または下です。ポイントは、DPテーブルを逆向き（右下から左上へ）に埋め、各セルで必要な最小体力を計算することです。各セルでは、dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) とします。体力は常に1以上でなければなりません。
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7グリッドDP問題の比較
グリッドDP問題は同じ構造を共有していますが、埋める方向と遷移に使う演算が異なります。Unique Pathsでは加算を使い、すべての方法を数えます。Min Path Sumでは最小値を使い、最適化します。Dungeon Gameでは逆向きに埋め、将来の位置から必要な体力を計算します。新しいグリッドDP問題に取り組むときは、次の3点を考えてください。(1) 各セルは何を表すか。(2) どの方向に埋めるか。(3) 近傍の値をどの演算で組み合わせるか。この3つに答えると、解法全体が明らかになります。
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')グリッドDPの計算量まとめ
ここで扱ったグリッドDP問題は、すべてO(m×n)時間で実行できます。空間計算量は、完全なテーブルではO(m×n)、1次元のローリング配列ではO(n)まで削減でき、グリッドをインプレースで変更できる場合は補助領域O(1)まで削減できます。面接では、O(m×n)の解法を示した後にO(n)空間への最適化にも触れてください。トレードオフを理解していることを示せます。また、すべての問題で、Unique Pathsの数式のような貪欲法による近道が存在しないかも検討してください。
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Unique Paths は dp[i][j] = dp[i-1][j] + dp[i][j-1] で2次元テーブルを埋め、組合せ論を使えばO(1)で計算できること、Min Path Sum は同じ構造を使いながら、加算をminに置き換えて最小パスコストを求めること、そしてすべてのグリッドDP問題は、セルごとに状態を定義し、遷移演算子（sum、min、max）を選ぶというパターンを共有していることを学びました。次は、2つの系列に対する2次元DPを使って、Longest Common Subsequenceを学びます。
よくある質問
「グリッド上のUnique Pathsと最小経路和」レッスンは無料ですか？
はい。「グリッド上のUnique Pathsと最小経路和」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「グリッド上のUnique Pathsと最小経路和」で何を学びますか？
障害物のある場合とない場合のUnique Pathsについて2D DPテーブルを埋め、経路上の値の合計を最小化する問題へ応用します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「グリッド上のUnique Pathsと最小経路和」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- グリッド上のUnique Pathsと最小経路和
- 最長共通部分列
- 編集距離（Levenshtein距離）
- 2D DPの空間最適化