Coding Interview Prep · レッスン

表形式によるボトムアップDP

トップダウン解を反復的なDPテーブルに変換し、直前の数個の値だけが必要な場合は空間計算量をO(n)からO(1)に削減します。

「表形式によるボトムアップDP」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

ボトムアップDP：表形式化アプローチ

ボトムアップDP（表形式化）では、最小の部分問題から始めて答えを表に埋め、最終的な答えまで積み上げます。下向きに再帰し、戻りながらキャッシュするのではなく、基礎となる部分問題から反復的に計算します。表は通常、1次元または2次元の配列で、各セルをすでに埋めたセルから計算します。これにより再帰を完全になくせます。呼び出しスタックも再帰上限も不要になり、キャッシュ局所性も向上します。

# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)

# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')

ボトムアップのフィボナッチ数列

ボトムアップのフィボナッチ数列では、dp[0..n]を左から右へ埋めます。i >= 2ではdp[i] = dp[i-1] + dp[i-2]です。基底ケースであるdp[0] = 0とdp[1] = 1は、配列に直接格納します。時間計算量はO(n)、完全な表を使う場合の空間計算量もO(n)です。dp[i]が直前の2つの値だけに依存すると分かれば、2つの変数を使って空間計算量をO(1)に削減できます。これがメモリ使用量を最適化する段階です。

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0  # base case
    dp[1] = 1  # base case
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Space-optimised to O(1):
def fib_optimised(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimised(50))  # 12586269025

ボトムアップのCoin Change

Coin Changeでは、ボトムアップの表をdp[0..amount]とし、dp[i]は金額iを作るために必要なコインの最小枚数を表します。dp[0] = 0（金額0にはコイン0枚）と初期化し、dp[1..amount] = infinityとします。金額iを1から目標値まで順に処理し、各コインを試します。i >= coinなら、dp[i] = min(dp[i], 1 + dp[i - coin])とします。答えはdp[amount]です。値がまだinfinityなら-1を返します。

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:  # can use this coin
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2: (5+6)
print(coin_change([2], 3))             # -1: impossible
print(coin_change([1, 2, 5], 11))      # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249))  # 20

計算順序：重要なポイント

計算順序は、ボトムアップDPの核心です。状態dp[i]について、依存するすべての状態を先に計算しておく必要があります。dp[i]がdp[i-1]とdp[i-2]に依存する1次元DPでは、左から右へ埋めます。dp[i][j]がdp[i-1][j]とdp[i][j-1]に依存する2次元DPでは、行ごとに（上から下、左から右へ）埋めます。コーディング前に必ず依存関係の矢印を描き、計算順序を確認してください。

# Fill order examples:

# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n

# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.

# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems

print('Draw dependencies first, then determine fill order')

ボトムアップLCS：2次元テーブル

最長共通部分列のボトムアップの表は(m+1) × (n+1)の大きさで、dp[i][j]はs1[:i]とs2[:j]のLCSを表します。基底ケースでは、dp[0][j] = dp[i][0] = 0です（空文字列と任意の文字列のLCSは0です）。行ごとに埋めます。s1[i-1] == s2[j-1]ならdp[i][j] = 1 + dp[i-1][j-1]、そうでなければdp[i][j] = max(dp[i-1][j], dp[i][j-1])です。答えはdp[m][n]です。

def lcs_bottom_up(s1, s2):
    m, n = len(s1), len(s2)
    # (m+1) x (n+1) table, initialised to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:         # characters match
                dp[i][j] = 1 + dp[i-1][j-1]
            else:                            # skip one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs_bottom_up('abcde', 'ace'))   # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB'))  # 4: 'BCAB' or 'BDAB'

メモリ使用量の最適化：ローリング配列

多くの2次元DPテーブルは、dp[i][j]が現在の行と直前の行だけに依存することに着目すれば、1次元（または2行）に削減できます。prevとcurrの2つの配列を保持するか、適切な順序で1つの配列を更新します。LCSでは、dp[i][j]はdp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]に依存するため、直前の行だけ保持すれば十分です。

def lcs_space_optimised(s1, s2):
    m, n = len(s1), len(s2)
    # Keep only one row (previous row state)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = 1 + prev[j-1]  # dp[i-1][j-1]
            else:
                curr[j] = max(prev[j], curr[j-1])  # dp[i-1][j] and dp[i][j-1]
        prev = curr
    return prev[n]

print(lcs_space_optimised('abcde', 'ace'))   # 3
# Space: O(n) instead of O(mn)

ボトムアップのHouse Robber

House RobberのボトムアップDPでは、dp[0..n-1]を埋めます。dp[i]は、家0から家iまでを対象にしたときの最大利益を表します。dp[0] = nums[0]、dp[1] = max(nums[0], nums[1])とし、i >= 2ではdp[i] = max(dp[i-1], dp[i-2] + nums[i])です。dp[i]は直前の2つの値だけに依存するため、2つの変数を使ってすぐに空間計算量をO(1)へ最適化できます。これは、2段階前までの依存関係を持つ1次元DPでよく使われるパターンです。

def rob_bottom_up(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]

    # Full table version: O(n) space
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

def rob_optimised(nums):
    # O(1) space: only need last two values
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob_optimised([2, 7, 9, 3, 1]))  # 12

グリッド上の最小パス和

Minimum Path Sum（LeetCode #64）では、右または下にだけ移動して、左上から右下まで値の合計が最小になる経路を求めます。2次元DPでは、dp[i][j]はセル(i,j)に到達するための最小合計を表します。dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])です。左から右、上から下の順に埋めます。基底ケースはdp[0][0] = grid[0][0]です。1行目は右方向だけ、1列目は下方向だけで埋めます。

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    # Fill first row (can only come from left)
    for c in range(1, cols):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    # Fill first column (can only come from above)
    for r in range(1, rows):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    # Fill rest of the table
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
    return dp[rows-1][cols-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7: 1+3+1+1+1

DPテーブルをその場で変更する

追加のメモリを使えない場合、入力グリッド自体をDPテーブルとして変更できることがあります。最小パス和では、grid[i][j]をそのセルに到達するための最小コストで上書きします。これにより追加の空間計算量をO(1)にできますが、入力データを破壊します。このトレードオフを必ず面接官に伝え、許容されるか確認してください。入力を保持する必要がある場合は、ローリング配列の方法を使います。

def min_path_sum_inplace(grid):
    rows, cols = len(grid), len(grid[0])
    # Modify grid in-place (O(1) extra space, destroys input)
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue  # starting cell
            elif r == 0:
                grid[r][c] += grid[r][c-1]  # first row
            elif c == 0:
                grid[r][c] += grid[r-1][c]  # first column
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[rows-1][cols-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

コインチェンジにおけるトップダウンとボトムアップの比較

どちらのアプローチもコインチェンジを最適に解きますが、実際の動作には違いがあります。トップダウンは記述しやすく、実際に到達可能な部分問題だけを計算します。ボトムアップは、指定されたコインでは到達できない金額（その場合は無限大のまま）も含め、0から目標値までのすべての金額を計算します。スパースな問題（到達可能な状態が少ない）ではトップダウンのほうが効率的で、密な問題ではボトムアップのほうがオーバーヘッドが小さくなります。

import functools

# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0: return 0
        if rem < 0: return float('inf')
        return 1 + min(dp(rem - c) for c in coins)
    r = dp(amount)
    return r if r != float('inf') else -1

# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_top([1,5,6,9], 11))    # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2

Unique Paths：古典的な2D DP

Unique Paths（LeetCode #62）は、m×nのグリッド上で右または下にのみ移動し、左上から右下まで到達する経路の数を数えます。漸化式は単純です。dp[i][j] = dp[i-1][j] + dp[i][j-1]—上から来る経路と左から来る経路を足します。基本ケースでは、最初の行全体と最初の列全体の経路数がそれぞれちょうど1になります（移動できる方向が1つしかないためです）。この2D DPはO(mn)時間で表を埋め、ローリング行を使えばO(n)空間に削減できます。

def unique_paths(m, n):
    # dp[i][j] = number of paths to reach cell (i,j)
    dp = [[1] * n for _ in range(m)]
    # Base: first row and first column are all 1
    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, 2))   # 3

# O(n) space rolling row:
def unique_paths_opt(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

print(unique_paths_opt(3, 7))  # 28

理解度チェック

このレッスンで学んだData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、表形式によるボトムアップDPと依存関係の矢印から埋める順序を決める方法、ローリング配列による空間最適化（O(mn)からO(n)）と2変数による追跡（O(n)からO(1)）、さらにFibonacci、コインチェンジ、LCS、House Robber、最小パス和のボトムアップ実装を学びました。次は、コインチェンジと最小コスト階段問題を最初から最後まで解きます。

よくある質問

「表形式によるボトムアップDP」レッスンは無料ですか？

はい。「表形式によるボトムアップDP」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「表形式によるボトムアップDP」で何を学びますか？

トップダウン解を反復的なDPテーブルに変換し、直前の数個の値だけが必要な場合は空間計算量をO(n)からO(1)に削減します。ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン3/4です。

「表形式によるボトムアップDP」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Coding Interview Prepに戻る