DSA Interview Prep · レッスン

区間DPのパターンと埋める順序

Q: 「区間DPのパターンと埋める順序」レッスンは無料ですか？

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

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

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

Q: 「区間DPのパターンと埋める順序」レッスンにはどのくらい時間がかかりますか？

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

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

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

区間DPの状態dp[i][j]を定義し、区間を長さの昇順で埋める必要がある理由を説明して、行列連鎖積でパターンを追跡します。

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

区間 DP とは

区間 DP は、状態 dp[i][j] がインデックス i から j までにまたがる部分問題の最適解を表す、動的計画法のパターンです。重要なポイントは、まず小さな区間を解き、そこから全体の範囲へと積み上げていくことです。このパターンは、部分問題の境界が範囲の左端と右端になる、行列連鎖乗算、回文分割、風船を割る問題などを自然にモデル化できます。

状態の定義とベースケース

区間 DP では、状態は dp[i][j] で、i <= j です。ベースケースは1要素だけの区間である dp[i][i] です。これは自明に解けます。たとえば、行列が1つだけなら乗算コストは0です。2要素の区間 dp[i][i+1] にも、単純な答えが得られることがよくあります。区間の長さ1から n まで、長さを増やしながら表を埋めます。

n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
    dp[i][i] = 0  # length-1 intervals

埋める順序: 長さの昇順

区間 DP で重要なのは表を埋める順序です。長い区間は短い部分区間に依存するため、長さ L+1 の区間を計算する前に、長さ L の区間をすべて計算しなければなりません。外側のループでは区間の長さを2から n まで繰り返し、中央のループで左端 i を設定し、右端を j = i + L - 1 として求めます。

n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for length in range(2, n + 1):      # interval length
    for i in range(n - length + 1): # left boundary
        j = i + length - 1          # right boundary
        for k in range(i, j):       # split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

行列連鎖乗算の設定

区間 DP の代表的な問題が行列連鎖乗算です。dims[0..n] で表される次元を持つ行列が与えられたとき、積を計算するために必要なスカラー乗算の最小回数を求めます。行列 A(p×q) と B(q×r) の乗算には、p*q*r 回の演算が必要です。dp[i][j] は、行列 i から j までを乗算する最小コストです。分割点 k によって、列を2つの部分列に分割する位置を決めます。

def matrix_chain_order(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

print(matrix_chain_order([10, 30, 5, 60]))  # 4500

DP 表をたどる

次元 [10, 30, 5, 60] の行列連鎖の例をたどってみましょう。これは3つの行列、A(10×30)、B(30×5)、C(5×60) を表します。dp[0][2] では、k=0 で分割すると、dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000 になります。また、k=1 で分割すると、dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500 になります。したがって、dp[0][2] = 4500 であり、これは最初に AB を乗算することで達成できます。

この埋める順序が機能する理由

dp[i][j] を計算するときは、[i, j-1] のすべての k について、dp[i][k] と dp[k+1][j] を参照します。どちらの部分区間も [i, j] より厳密に短い長さになります。長さの小さい順に繰り返すことで、必要なすべての部分区間が、参照する前に計算されます。これが区間 DP でこの順序が正しいことの基本的な根拠です。短い区間は常に長い区間の依存先になります。

メモ化を使ったトップダウン区間 DP

区間 DP は、メモ化を使ったトップダウンでも実装できます。区間 [i, j] の最適コストを返す再帰関数 solve(i, j) を記述し、結果を辞書にキャッシュします。再帰によって表を埋める順序が自動的に処理されます。トップダウンは考え方を整理しやすいことが多い一方で、関数呼び出しのオーバーヘッドが発生する可能性があります。大きな入力では、実際にはボトムアップの方が高速です。

from functools import lru_cache

def matrix_chain_memo(dims):
    n = len(dims) - 1
    
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == j:
            return 0
        return min(
            solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
            for k in range(i, j)
        )
    
    return solve(0, n-1)

print(matrix_chain_memo([10, 30, 5, 60]))  # 4500

時間計算量と空間計算量

区間 DP には、すべての組 (i, j) に対応するO(n²) 個の状態があり、各状態で O(n) 個の分割点を調べるため、全体の時間計算量は O(n³)です。空間計算量は DP 表のO(n²)です。100個の行列による行列連鎖乗算の場合でも、これは1,000,000回の演算であり、十分に現実的です。このパターンは多くの難しい LeetCode 問題に登場し、構造が直感的ではないため FAANG の面接でも好んで使われます。

最適解の復元

コストだけでなく実際の括弧付けを復元するには、各状態で最小値を達成した k を記録する別の split[i][j] 表を保存します。その後、分割を再帰的に読み取ります。reconstruct(i, j) は、[i, split[i][j]] と [split[i][j]+1, j] に対して再帰を行うことで、最適なグループ化を出力します。この手法は、すべての区間 DP 問題に適用できます。

def matrix_chain_with_split(dims):
    n = len(dims) - 1
    dp = [[0]*n for _ in range(n)]
    split = [[0]*n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k
    return dp[0][n-1], split

任意の区間 DP 問題のテンプレート

区間 DP の汎用テンプレートは3つの部分で構成されます。(1) 1要素のベースケースを初期化します。(2) 長さを増やしながらループし、各長さについて有効な左端をループして右端を求めます。(3) 各区間についてすべての分割点を調べ、問題固有の漸化式を適用します。問題ごとに変わるのは、最も内側のループにある漸化式だけです。

def interval_dp_template(n, base_cost, split_cost):
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = base_cost(i)  # problem-specific base case
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                # problem-specific recurrence
                candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
                dp[i][j] = min(dp[i][j], candidate)
    
    return dp[0][n-1]

区間 DP の代表的な問題

区間 DP を使う問題には、行列連鎖乗算（演算回数を最小化）、風船を割る問題（コインを最大化）、Strange Printer（印刷回数を最小化）、多角形の最小スコア三角形分割、回文分割 IIなどがあります。どの問題も同じ表の埋め方の骨格を使いますが、漸化式は異なります。区間や列に対する最適値を求め、その内部の任意の位置で分割できる問題では、このパターンを見抜いてください。

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認してください。

レッスンのまとめ

このレッスンでは、区間 DP では dp[i][j] を使って範囲に対する最適解を表すこと、部分区間を先に計算できるよう、区間の長さを増やす順序で表を埋める必要があること、そして汎用テンプレートの時間計算量は O(n³)、空間計算量は O(n²) であることを学びました。次は、このパターンを使って最長回文部分列と最長回文部分文字列を扱います。

よくある質問