2D DPの空間最適化
DPテーブルの現在行と直前行だけを保持し、LCSと編集距離の空間計算量をO(mn)からO(min(m,n))に削減します。
「2D DPの空間最適化」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
2D DPで空間が重要な理由
長さ1000の文字列に対する2D DPテーブルには、1000×1000 = 1,000,000個のセルが必要で、64ビット整数ではおよそ8 MBになります。より長い系列（DNAアラインメントや大規模なテキスト差分）では、これは現実的でなくなります。重要な観察は、ほとんどの2D DPの漸化式が現在の行と直前の行だけを参照することです。そのため、テーブル全体を1つまたは2つの1次元配列に圧縮できます。これが2D DPの空間最適化の核心です。
# Full 2D DP: O(mn) space
# LCS for 1000-char strings
m, n = 1000, 1000
dp_2d_size = m * n * 8 # bytes (64-bit ints)
print(f'2D table: {dp_2d_size:,} bytes = {dp_2d_size//1024} KB')
# 1D rolling array: O(n) space
dp_1d_size = n * 8
print(f'1D array: {dp_1d_size:,} bytes = {dp_1d_size} bytes')
print(f'Space saving: {dp_2d_size // dp_1d_size}x')ローリング配列パターン
ローリング配列パターンでは、完全な2Dテーブルを、直前の行を表す1次元配列に置き換えます。行iを計算するときは、現在のdp[j]（まだ直前の行のdp[i-1][j]を保持しています）と、更新直後のdp[j-1]（dp[i][j-1]です）を使って各セルを更新します。diagonal変数には、上書きされる前のdp[i-1][j-1]を保持します。このパターンは、LCS、編集距離、その他ほとんどの2D DP問題に適用できます。
# Rolling array template for 2D DP
# Before update: dp[j] holds dp[i-1][j] (previous row)
# After update: dp[j] holds dp[i][j] (current row)
def rolling_array_template(grid):
m, n = len(grid), len(grid[0])
dp = [0] * (n + 1) # represents one row
for i in range(1, m + 1):
diag = 0 # stores dp[i-1][j-1] before overwrite
for j in range(1, n + 1):
temp = dp[j] # save dp[i-1][j] before overwriting
# compute dp[i][j] using dp[j] (above) and dp[j-1] (left) and diag
dp[j] = diag + dp[j] + dp[j-1] # placeholder logic
diag = temp
return dp[n]O(min(m,n))空間でのLCS
LCSでは、text1が短い文字列になるようにします（nを小さくするためです）。サイズがn+1の1次元配列を確保します。行ごとに処理します。各セルでは、temp = dp[j]（これはdp[i-1][j]です）を保存します。次に、文字が一致する場合はdp[j] = diag + 1、それ以外の場合はdp[j] = max(dp[j], dp[j-1])とします。最後にdiag = tempを設定します。すべての行を処理すると、dp[n]にLCSの長さが格納されます。
def lcs_space_opt(text1, text2):
# Ensure text2 is the shorter one
if len(text1) < len(text2):
text1, text2 = text2, text1
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
diag = 0
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_space_opt('ABCBDAB', 'BDCABA')) # 4
print(lcs_space_opt('AGGTAB', 'GXTXAYB')) # 4O(n)空間での編集距離
編集距離にも同じローリングパターンを使用します。最初の1次元配列は行0を表し、dp[j] = j（j文字を挿入）とします。各行iでは、dp[0] = i（i文字を削除）を設定し、更新前にdiag = dp[0]を保存します。内側のループではtemp = dp[j]を保存し、挿入（dp[j-1]+1）、削除（dp[j]+1）、置換（diag + cost）から新しい値を計算し、その後diag = tempを設定します。
def edit_dist_opt(s, t):
m, n = len(s), len(t)
dp = list(range(n + 1)) # row 0: dp[0][j] = j
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0] before dp[0] update
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
cost = 0 if s[i-1] == t[j-1] else 1
dp[j] = min(
dp[j-1] + 1, # insert
dp[j] + 1, # delete
diag + cost # replace or match
)
diag = temp
return dp[n]
print(edit_dist_opt('horse', 'ros')) # 3
print(edit_dist_opt('intention', 'execution')) # 5O(n) 空間での Min Path Sum
グリッド上の Min Path Sum では、1次元のローリング配列を最初の行の累積和として初期化します（最初の行の各セルへ到達する方法は1つだけです）。後続の各行では左から右へ更新します。更新前の dp[j] は上の行の値（dp[i-1][j]）であり、直前に更新された dp[j-1] は左のセルの値です。最小パス合計では対角セルを必要としないため、ここでは対角要素は必要ありません。
def min_path_sum_opt(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
# Update first column (only from above)
dp[0] += grid[i][0]
for j in range(1, n):
# min of above (dp[j] = old) and left (dp[j-1] = updated)
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_opt(grid)) # 7対角要素へのアクセスが必要な場合
すべての2次元 DP 問題を単純なローリング配列で圧縮できるわけではありません。対角要素 dp[i-1][j-1] が dp[j] の上書き後に必要になる問題があるためです。解決方法は常に同じです。更新する前に temp = dp[j] を保存し、それを次の列の計算で diag として使います。この1セル先読みで、3方向の漸化式（LCS、編集距離）にもきれいに対応できます。
# Recap: the diagonal save pattern
# Without it: dp[j-1] updated (left) and dp[j] about to be overwritten
# With it:
def show_diagonal_pattern(s1, s2):
n = len(s2)
dp = [0] * (n + 1)
for ch1 in s1:
diag = 0 # was dp[i-1][0] = 0 for LCS
for j, ch2 in enumerate(s2, 1):
temp = dp[j] # SAVE before overwrite
if ch1 == ch2:
dp[j] = diag + 1 # use saved diagonal
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp # advance diagonal
return dp[n]
print(show_diagonal_pattern('ABCBDAB', 'BDCABA')) # 42D ナップサックの空間最適化
0/1 ナップサック問題も空間最適化の恩恵を受けます。完全な2次元テーブルの次元は (n_items+1) × (capacity+1) です。ローリング配列を使うと O(capacity) まで削減できます。LCS や編集距離との重要な違いは、capacity 次元を逆順（高い値から低い値へ）に反復することです。これにより、各アイテムが高々1回しか数えられないことが保証されます。順方向に反復すると、同じアイテムを複数回選べるようになります。
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Reverse order: prevents using the same item twice
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
cap = 7
print(knapsack_01(weights, values, cap)) # 9 (items 3+4: weight 3+4=7, value 4+5=9)順方向と逆方向の反復
内側のループをどちらの方向に反復するかを知ることは重要です。0/1 ナップサックでは逆順にします（各アイテムは高々1回しか使えません。以前の状態を参照することで再利用を防ぎます）。unbounded knapsack では順方向にします（各アイテムを再利用でき、更新済みの状態を参照することで複数回使えます）。ここを間違えると、気付かないうちに 0/1 ナップサックが unbounded knapsack に、またはその逆に変わってしまいます。方向を選ぶ前に、必ず制約を確認してください。
# 0/1 Knapsack: each item used AT MOST ONCE → iterate reverse
def knapsack_01_demo(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w-1, -1): # REVERSE
dp[c] = max(dp[c], dp[c-w] + v)
return dp[cap]
# Unbounded Knapsack: items can be reused → iterate forward
def knapsack_unbounded(weights, values, cap):
dp = [0] * (cap + 1)
for c in range(1, cap + 1):
for w, v in zip(weights, values):
if c >= w:
dp[c] = max(dp[c], dp[c-w] + v) # FORWARD
return dp[cap]
print(knapsack_01_demo([2,3],[3,4],5)) # 7
print(knapsack_unbounded([2,3],[3,4],5)) # 8 (use weight-2 twice: 3+3=6? or 4+... )O(n) 空間での Unique Paths
Unique Paths では、テーブル全体を1行だけで置き換えられます。すべてのセルを1（最初の行の値）で初期化します。後続の各行では左から右へ dp[j] += dp[j-1] と更新します。漸化式が使用するのは上のセル（dp[j]、更新前の現在の値）と左のセル（dp[j-1]、更新済みの値）だけなので、対角要素は必要ありません。これは最も単純な 2D→1D 圧縮です。
def unique_paths_opt(m, n):
dp = [1] * n # first row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # above (dp[j]) + left (dp[j-1])
return dp[n-1]
# With obstacles
def unique_paths_obstacles_opt(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1
for i in range(m):
if grid[i][0] == 1: dp[0] = 0 # blocked column
for j in range(1, n):
if grid[i][j] == 1: dp[j] = 0 # blocked
else: dp[j] += dp[j-1]
return dp[n-1]
print(unique_paths_opt(3, 7)) # 28
print(unique_paths_obstacles_opt([[0,0,0],[0,1,0],[0,0,0]])) # 2複雑な漸化式のための2行バッファ
漸化式で2行以上前のセルが必要な場合（たとえば、一部の区間 DP の派生形や 3D DP の縮約）には、2行バッファを使います。prev と curr の配列を保持し、各行の後で交換します。これにより、空間計算量は O(2n) = O(n) になります。k 行前まで参照する漸化式では、k 個の配列を循環バッファとして保持します。これは1行のローリング配列パターンを一般化したものです。
def lcs_two_row_buffer(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1) # dp[i-1]
curr = [0] * (n + 1) # dp[i]
for i in range(1, m + 1):
curr[0] = 0
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, prev # swap (curr becomes prev)
return prev[n] # after swap, prev holds the last computed row
print(lcs_two_row_buffer('ABCBDAB', 'BDCABA')) # 4空間最適化が不可能な場合
空間最適化は常に可能とは限りません。最適解の復元（値だけでなく解そのものの復元）が必要な場合、一般にバックトラッキングのために完全なテーブルが必要です。回避策には次のものがあります。(1) 同じサイズの独立した判定テーブルを保存する。(2) Hirschbergのアルゴリズムを使う。このアルゴリズムは問題を中間点で再帰的に分割することで、復元を含めて LCS を O(mn) 時間、O(min(m,n)) 空間で計算します。(3) 復元が必要な場合は O(mn) 空間を受け入れる。
# When reconstruction needed: must keep full table or use Hirschberg
# Hirschberg's idea: compute LCS length in O(n) space at midpoint of s1,
# recurse on left and right halves. O(mn) time, O(n) space + reconstruction.
# For interview: mention the trade-off
# 'I can reduce to O(n) space if only the value is needed.
# To also reconstruct the sequence, I need the full O(mn) table
# or a more complex divide-and-conquer approach.'
print('Space opt: O(n) for length only')
print('Full table: O(mn) needed for reconstruction')クイックチェック
このレッスンの Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、直前の行だけが必要な場合、ローリング1次元配列を使って2D DP テーブルを O(n) 空間に圧縮できること、対角変数パターン（上書き前に temp を保存する方法）によって dp[i-1][j-1] が必要な漸化式に対応できること、そして0/1 ナップサックでは capacity を逆順に反復し、unbounded knapsack では順方向に反復することを学びました。次は、全探索アルゴリズムの基盤である Backtracking テンプレート、Choose、Explore、Unchoose を学びます。
よくある質問
「2D DPの空間最適化」レッスンは無料ですか？
はい。「2D DPの空間最適化」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「2D DPの空間最適化」で何を学びますか？
DPテーブルの現在行と直前行だけを保持し、LCSと編集距離の空間計算量をO(mn)からO(min(m,n))に削減します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「2D DPの空間最適化」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。