動的計画法の思考法 — 全探索を «状態» に畳み、表に落とすまで

動的計画法（dynamic programming、以下 DP）は、競技プログラミングの道具のなかで «解法を思いつけるかどうか» の差が最も出やすく、暗記で乗り切ろうとして最も失敗しやすい道具です。ナップサックの漸化式を覚えていても、初見の問題でその形にたどり着けなければ使えません。

DP はアルゴリズムではなく、全探索を書き直すための設計手順です。覚えるべきなのは個々の漸化式よりも、全探索から漸化式に至る手順のほうです。この記事では、その手順を段階に分けて動くデモで確かめ、典型的な型、遷移の高速化、実務での応用へと進みます。

1. DP は「全探索の書き直し」である

1.1 DP で解ける問題の 2 つの条件

ある問題が DP で解けるとき、ほぼ必ず次の 2 つが成り立っています。

• 最適部分構造（optimal substructure）: 最適解が、部分問題の最適解から組み立てられる。
• 部分問題の重複（overlapping subproblems）: 素朴な再帰が、まったく同じ部分問題を何度も解いている。

前者だけなら分割統治（マージソートなど）で十分で、後者だけならキャッシュで済みます。両方が揃ったときに、部分問題に名前を付けて表に保存すると、各部分問題は 1 回ずつ解くだけになります。部分問題の種類が多項式個なら、指数時間の計算が多項式時間に下がります。

Richard Bellman が 1950 年代に定式化した最適性の原理（principle of optimality）は、最適部分構造と同じ性質を、方策（決定の列）の言葉で述べたものです。

最適な方策は、最初の状態と最初の決定が何であっても、その決定で移った先の状態から見たとき、残りの決定列がやはり最適な方策になっている。

なお「dynamic programming」という名前は、数学的研究に否定的だった当時の国防長官の目を意識してあえて選んだ、と Bellman は自伝 Eye of the Hurricane（1984）で述べています。ここでの programming は「計画法」であり、プログラミング言語とは関係ありません。

1.2 貪欲法との分岐点

DP と貪欲法は、どちらも「1 手ずつ決める」構造をしています。違いは、局所的な最良手が大域最適の一部だと保証できるかです。

貪欲法を使うには、それが正しいことを証明する必要があります。代表的な道具は 2 つです。1 つは交換論法（exchange argument）で、2 つの選択を入れ替えても解が悪化しないことを示します。最適解の 1 手を貪欲の 1 手に取り替える形と、隣り合う 2 要素の順序を入れ替える形があり、後者の実例は 3.5 節で扱います。もう 1 つはマトロイド構造の確認です。「独立な集合の族」がある公理を満たせば貪欲法の最適性が保証される、という一般論で、最小全域木の Kruskal 法がその例です。証明できないなら、最初の 1 手を全通り試して残りを再帰に任せる、つまり DP に落とすのが安全です。逆に、貪欲法の正しさを証明できる問題に DP を使うと、計算量とコード量が無駄に増えます。

硬貨の額面の組（硬貨系）について、貪欲法が常に最適になるか（canonical か）は判定できます。Pearson（2005）は、$n$ 種類の硬貨系を $O(n^3)$ で判定するアルゴリズムを与えています。貪欲法でよいかどうかは、問題文だけでなく入力によっても決まるということです。

1.3 全探索からの分岐図

この図では、DP は全探索を圧縮したものとして位置づけられます。DP を思いつくとは、正しい圧縮の軸を見つけることです。

2. 出発点は必ず全探索

2.1 題材：Frog 1

題材は AtCoder の Educational DP Contest（以下 EDPC）の A 問題「Frog 1」です。

高さ $h_0, h_1, \dots, h_{N-1}$ の石が並んでいる。カエルは石 0 から出発し、石 $i$ にいるとき石 $i+1$ か $i+2$ に飛べる。石 $i$ から石 $j$ へ飛ぶコストは $|h_i - h_j|$。石 $N-1$ に着くまでの最小コストは？

まず、工夫せずに全探索を書きます。各時点で決めることは、1 段飛ぶか 2 段飛ぶかです。

def solve(h):
    n = len(h)
 
    def f(i):  # 石 i にたどり着くまでの最小コスト
        if i == 0:
            return 0
        if i == 1:
            return abs(h[1] - h[0])
        return min(
            f(i - 1) + abs(h[i] - h[i - 1]),
            f(i - 2) + abs(h[i] - h[i - 2]),
        )
 
    return f(n - 1)

このコードは正しい答えを返しますが、遅すぎます。どれだけ遅いかは、再帰木を描くと分かります。

2.2 再帰木を見る

メモ化を OFF にして再生すると、f(3), f(2), f(1) が何度も現れます。呼び出し回数は $T(i) = 1 + T(i-1) + T(i-2)$、すなわち $2F(i+1) - 1$ で、フィボナッチ数の速度で増えます（$T(0) = T(1) = 1$ から順に $T(2) = 3$、$T(3) = 5$、$T(4) = 9$、$T(5) = 15$。デモの木のノード数と一致することを確かめてみてください）。$N = 45$ なら約 22.7 億回です。

一方、引数の種類は $N$ 通りしかありません。同じ引数に対して同じ値を返す関数を、何度も計算し直しているわけです。そこで、一度計算した結果を引数ごとに保存して再利用します。これがメモ化です。

from functools import cache
 
def solve(h):
    n = len(h)
 
    @cache
    def f(i):
        if i == 0:
            return 0
        if i == 1:
            return abs(h[1] - h[0])
        return min(
            f(i - 1) + abs(h[i] - h[i - 1]),
            f(i - 2) + abs(h[i] - h[i - 2]),
        )
 
    return f(n - 1)

functools.cache（Python 3.9 以降。それ以前は lru_cache(maxsize=None)）を 1 行足すだけで、指数時間が線形時間になります。デモでメモ化を ON にすると、計算済みの枝が刈られ、木が小さく潰れます。

2.3 メモ化が正しい条件

メモ化が正しいのは、f が引数だけで戻り値が決まる純粋関数のときです。関数の外側にある可変状態（訪問済みフラグ、グローバルなカウンター、乱数）を読んでいると、同じ引数でも呼び出し文脈によって答えが変わります。それでもキャッシュは最初の答えを返し続けるので、エラーも例外も出ないまま結果だけが狂います。

実装では次の 2 点を確認します。

• 関数が読んでいる変数のうち、実行中に変化するものがすべて引数に入っているか。
• 引数に入れるべき情報を「入れなくても大丈夫だろう」と省略していないか。

2 点目は、3 章で扱う «状態設計» の問題です。

2.4 計算量は「状態数 × 遷移数」

この先で使う «状態» と «遷移» を、いま書いたコードに即して定義します。

• 状態: メモ化した関数 f の引数の組のこと。状態数はその引数が取りうる値の種類数です。Frog 1 では引数は i だけなので、状態数は $N$ 個。
• 遷移: 1 つの状態から別の状態への 1 手のこと。遷移数は、f を 1 回実行する中で行われる再帰呼び出しの本数です。Frog 1 では min(...) の中の 2 項、つまり $i-1$ と $i-2$ の 2 本。

メモ化された関数は、実際に呼ばれた引数それぞれにつき、ちょうど 1 回だけ本体が走ります。だから全体の仕事量は「本体が走る回数 × 1 回あたりの仕事」であり、DP の計算量は、ほぼ常に次の掛け算で見積もれます。

Frog 1 なら $N \times 2 = O(N)$ です。この掛け算は実装前に必ず暗算してください。制約が $N \le 10^5$ なのに状態数 $N^2$ の設計を思いついたら、その時点で捨てます。競技プログラミングでの目安として、1〜2 秒の実行時間制限に収まるのは、C++ で単純な演算 $10^8$ 回程度、Python で $10^6 \sim 10^7$ 回程度です。

2.5 ここから先の地図

ここまでで、全探索を書き、重複に気づき、引数を状態と呼び直し、計算量を掛け算で見積もる、という DP の骨格が揃いました。3 章以降は、章によって読み方が違います。

通読が必要なのは 5 章までです。6 章の各節は「問題の定義 → 状態 → 遷移 → 実装 → 落とし穴」の順で書いてあり、それぞれ単独で読めます。知らない型に出会ったときに、該当する節を開いてください。

3. 状態とは「未来に効く情報の最小集合」

3.1 定義

DP における状態を、実用的にはこう定義できます。

ここまでの決定のうち、この先の最適な決め方に影響するものだけを残した要約。

これは確率過程でいう Markov 性、統計でいう十分統計量と同じ考え方です。ここまでの経路をすべて覚える必要はなく、この先を最適に決めるのに必要な分だけ覚えれば足ります。要約が小さいほど状態数が減り、DP が速くなります。

3.2 状態設計に失敗する典型例

最長増加部分列（Longest Increasing Subsequence、以下 LIS）を例にします。

数列 $a_0, a_1, \dots, a_{n-1}$ が与えられる。添字が増加する順に選んだ部分列のうち、値が狭義単調増加になっているもので、最も長いものの長さを求めよ。

ここでいう部分列は「連続していなくてよい」ものです（連続を要求するのは «部分配列» で、次の 3.3 節で扱います）。たとえば $a = [3, 1, 4, 1, 5, 9, 2, 6, 5]$ なら、添字 1, 2, 4, 5 を選んだ $1 < 4 < 5 < 9$ や、添字 1, 2, 4, 7 の $1 < 4 < 5 < 6$ が長さ 4 で、これが最長です。

素朴に

dp[i] = a[0..i] の中の最長増加部分列の長さ

と置くと、dp[i] から dp[i+1] への遷移が書けません。a[i+1] を末尾に付け足せるかどうかは、その増加列の末尾の値に依存しますが、この状態はそれを覚えていないからです。上の例で dp[5] = 4 と分かっても、その長さ 4 の列が $1<4<5<9$（末尾 9）なのか別のものなのかが分からず、次の $a_6 = 2$ を足せるか判定できません。

正しい定義は次のとおりです。

dp[i] = a[i] を末尾とする最長増加部分列の長さ

「$i$ 番目まで見た」ではなく「$i$ 番目で終わる」に変えると、末尾の値が a[i] に固定され、遷移が書けるようになります。

dp[i] = 1 + max{ dp[j] | j < i かつ a[j] < a[i] }   （該当する j がなければ 1）
答え  = max(dp[0], ..., dp[n-1])

最長の増加列が最後の要素で終わるとは限らないので、「$i$ で終わる」と定義した DP では、答えは dp[n-1] ではなく dp 全体の最大値です。状態の定義を変えると答えの取り出し方も変わるので、DP を書くたびに両者が対応しているか確認してください。

遷移が書けないときは、状態が足りていません。これは最もよく遭遇する詰まり方で、状態を見直すべきだという分かりやすい合図でもあります。LIS の $O(n \log n)$ 版は 6.2 節で扱います。

3.3 最小の DP — 最大部分配列和

「$i$ で終わる」への言い換えは、配列 $a$ の部分配列の和の最大値を求める問題にも効きます。

素朴には全区間 $O(n^2)$ 通りを試します。ここで状態を「$a[i]$ で終わる部分配列の和の最大値」と置くと、遷移が 1 行で書けます。

dp[i] = max(a[i], dp[i-1] + a[i])
答え  = max(dp[0], dp[1], ..., dp[n-1])

遷移は、直前まで伸ばしてきた和に $a[i]$ を足すか、$a[i]$ から新しく始めるかの 2 択です。dp[i-1] しか参照しないので変数 2 つで済み、表は要りません。

def max_subarray(a):
    if not a:
        raise ValueError("空の配列には «空でない部分配列» が存在しません")
    best = cur = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)   # dp[i]
        best = max(best, cur)   # 答えの更新
    return best

これが Kadane のアルゴリズム（Jay Kadane, 1977。Bentley の Programming Pearls で広まりました）で、$O(n)$ 時間、$O(1)$ 空間で動きます。DP に表が必須ではないことがよく分かる例です。必要な表の大きさは、«状態の個数» ではなく «同時に生きている状態の個数» で決まります。

なお、この実装は空の部分配列を許しません。全要素が負のとき、空を許す定義なら答えは 0、許さない定義なら最大要素です。best = cur = 0 で始めると後者で誤答します。どちらの定義かは問題文で確認してください。

3.4 状態を «増やす» ことで解ける問題

状態を意図的に増やして解く問題も多くあります。

表の 1 行目の例として、EDPC C（Vacation）を解きます。「$N$ 日間、毎日 A・B・C の 3 種類の活動から 1 つを選ぶ。$i$ 日目に活動 A を選ぶと幸福度 $a_i$（B なら $b_i$、C なら $c_i$）を得る。ただし 2 日連続で同じ活動は選べない。幸福度の合計の最大値は？」という問題です。

dp[day] だけでは遷移が書けません。「$day$ 日目までの最大値」を知っていても、その最大値を出したときに最後に何を選んだかが分からないと、次の日に選べる活動が決まらないからです（3.2 節の LIS と同じ詰まり方です）。そこで、最後に選んだものを状態に足します。

dp[day][last] = day 日目に活動 last を選んだときの、そこまでの幸福度の合計の最大値
dp[day][last] = happiness[day][last] + max{ dp[day-1][prev] | prev ≠ last }
答え = max(dp[N-1][A], dp[N-1][B], dp[N-1][C])
基底  = dp[0][last] = happiness[0][last]   （初日は «直前» の制約がない）

状態数は $N \times 3$、遷移数は 2（自分以外の 2 種類）なので $O(N)$ です。足した次元は計算量を定数倍しか増やさず、書けなかった遷移を書けるようにしました。状態を増やすと得られるのは、典型的にはこの効果です。

状態設計では、足りないなら足し、多すぎるなら畳むという両方向の調整をします。

3.5 状態を «減らす» 4 つの定石

状態数が多すぎるときに使う手は、ほとんどが次の 4 つです。

(a) 順序を固定する。「どの順に処理しても答えが同じ」なら、あらかじめソートして単調性（ここでは «処理順に沿って制約が緩む/きつくなる» という向きの一貫性）を作ると、状態に «順序» を持たなくて済みます。逆に順序が効く問題でも、隣接する 2 要素を交換したときの損得を比べる交換論法で、最適な処理順が先に決まることがあります。

EDPC X（Tower）がこの形です。問題は「重さ $w_i$、耐荷重 $s_i$、価値 $v_i$ のブロックを積み上げる。各ブロックについて、その上に載っているブロックの重さの合計が $s_i$ を超えてはならない。価値の合計を最大化せよ」です。

隣り合う 2 つ $i, j$ だけを取り出し、その 2 つの上に載る重さの合計を $W$ とします。$i$ を上・$j$ を下に置けるのは、$i$ が耐えられて（$W \le s_i$）かつ $j$ も耐えられる（$W + w_i \le s_j$）ときなので、

i が上: W <= min(s_i, s_j - w_i)
j が上: W <= min(s_j, s_i - w_j)

この 2 つを比べます。«$j$ を上» の上限は $\min$ なので、必ず $s_i - w_j$ 以下です。一方、«$i$ を上» の上限の 2 項は、どちらも $s_i - w_j$ 以上になります。$s_i \ge s_i - w_j$ は重さが正であることから、$s_j - w_i \ge s_i - w_j$ は次の同値関係から従います。

したがって $w_i + s_i \le w_j + s_j$ なら、$\min$ のどちらの項が効いていても、«$i$ を上» の許容量が «$j$ を上» を下回ることはありません。$w + s$ が小さいものを上に置くほうが、許容できる $W$ が同じか大きい（＝損をしない）わけです。この比較はどのブロックを選ぶかに依存しないので、$w_i + s_i$ の昇順に並べ替えれば、あとは «その順に並べた列に対する 0-1 ナップサック»（6.1 節）になります。

(b) 対称性で畳む。「$i$ と $j$ を入れ替えても同じ」「集合の補集合を取っても同じ」なら、片側だけを持てば状態は半分になります。たとえば「$N$ 人を 2 チームに分ける」問題でチームに区別がないなら、$(S, \bar{S})$ と $(\bar{S}, S)$ は同じ分け方なので、「人 0 は必ずチーム 1」と固定すれば $2^N$ が $2^{N-1}$ になります。逆に、チームに名前がついている（区別がある）場合にこの固定をすると、解の半分を捨ててしまいます。

(c) 絶対量ではなく差を持つ。 2 つのグループの合計 $(A, B)$ を両方覚える必要はなく、$A - B$ だけで足りることがあります。「品物を 2 つの山に分け、重さの差を最小化する」問題は、$(A, B)$ の 2 次元ではなく «差» の 1 次元、あるいは「片方の山の重さとして到達可能な値の集合」で解けます。

(d) 最適化ではなく到達可能性に落とす。「最大値」ではなく「作れるか否か」だけでよいなら、bool の表になり、ビット並列化（6.9 節の $O(nW/64)$）が使えます。

いずれも「その情報は本当に未来に効くのか？」という 3.1 節の問いに戻って判断します。

4. 設計手順を型にする

ここまでの話を、初見の問題に使える 6 ステップの手順にまとめます。

難しいのはステップ 2 と 5 です。ステップ 2（何を覚えれば十分か）には発想が必要で、ステップ 5（計算量の見積もり）は実装前に設計の失敗を見つける安全弁になります。ステップ 3・4・6（状態を引数として書き下す、遷移と基底を書く、評価順序を決める）は、2 が決まればほぼ機械的に進められます。

4.1 ステップ 6 の「依存が DAG か」について

DP は本質的に有向非巡回グラフ（DAG）上の最短経路です。状態を頂点、遷移を辺、遷移コストを辺の重みとすると、DP の答えは始点から終点への最短経路（問題によっては最長経路、全経路の総和、確率最大の経路）になります。

有向グラフは「A から B へ」という向きのある辺で頂点をつないだもの、非巡回（acyclic）は「辺をたどって元の頂点に戻ってこられない」こと、トポロジカル順序は「すべての辺が前から後ろへ向かうように頂点を一列に並べた順序」のことです。DP に翻訳すると、頂点 = 状態、辺 = 遷移、そして「dp[x] を計算する前に dp[y] が確定していなければならない」という依存関係が辺の向きにあたります。Frog 1 なら、石 $i$ が頂点で、$i \to i+1$ と $i \to i+2$ が辺です。添字の小さい順に並べればすべての辺が前から後ろを向くので、これがトポロジカル順序になります。

この見方をすると、次の 3 点がまとめて説明できます。

• 評価順序 = トポロジカル順序。ループの向きを間違えるとは、トポロジカル順序を守っていないということ。
• 依存に閉路があると、そのままでは DP にならない。閉路を扱うには、(a) 辺数などの次元を足して層状の DAG に開く（Bellman–Ford）、(b) 順序を貪欲に確定させる（Dijkstra、辺の重みが非負のとき）、(c) 表全体を «値が変わらなくなるまで» 何周も更新し続ける（価値反復。9.6 節で扱います）のいずれかが必要になる。
• 最長経路は一般のグラフでは NP 困難だが、DAG では線形時間。これは EDPC G がそのまま示している。

DP は、グラフのトラバーサルアルゴリズム で扱った BFS や Dijkstra の最短経路を、«状態空間» に一般化したものとも読めます。

4.2 同じ表で別の問題を解く — 半環という見方

Frog 1 で「最小コスト」ではなく「石 0 から石 $N-1$ への行き方は何通りあるか」を聞かれたとします。書き換えが必要なのは、実質 1 行だけです。

最小コスト: dp[i] = min( dp[i-1] + cost1 , dp[i-2] + cost2 )
行き方の数: dp[i] =      dp[i-1] * 1      +  dp[i-2] * 1
初期値      : 最小コストは dp[0] = 0、行き方の数は dp[0] = 1

min だったところが + に、コストの + だったところが × になっています（行き方を数えるときは 1 本の辺の重みが「1 通り」なので、掛けても値が変わらず消えます）。ループも状態も走査順もそのままです。

この「演算だけ差し替える」操作は、半環（semiring）、つまり足し算にあたる演算 $\oplus$ と掛け算にあたる演算 $\otimes$ の組を取り替える操作として統一的に説明できます。$\oplus$ は「複数の経路から 1 つの値にまとめる」役、$\otimes$ は「経路に沿ってコストをつなぐ」役です。

初期値が 0 から 1 に変わるのも、この対応で説明できます。dp[0] に置くべきなのは「$\otimes$ でつないでも相手が変わらない値（$\otimes$ の単位元）」で、最小コスト版の $\otimes$ は足し算だから 0、数え上げ版の $\otimes$ は掛け算だから 1 です。これと対になるのが「$\oplus$ でまとめても影響しない値（$\oplus$ の単位元）」で、こちらは «そんな状態は存在しない» を表す値になります。最小化なら $\infty$、数え上げなら 0 です。範囲外の dp[-1] は «そんな行き方はない» なので、数え上げでは 0 として扱うことになり、結果として dp[1] = dp[0] = 1 です。

実装では、最小コストを求める DP を書いたあとで、同じ遷移で作れる場合の数が必要になっても、同じループのまま min を + に、+ を × に置き換えるだけで済みます。ただし、この置き換えで数えられるのは作り方の総数で、最小コストを達成する方法の数ではありません。後者が欲しいときは、$(\text{最小値},\ \text{その最小値を達成した個数})$ の組を 1 つの元とする半環に取り替えます。この半環の $\oplus$ は最小値を取り、最小値が同じなら個数を足します。

数え上げ版では、最小コストと違って値が指数的に増えるので、64 ビット整数に収まらなくなります。そのため問題文では $\bmod\ 10^9+7$ のような指定がつくのが普通で、加算・乗算のたびに剰余を取ります（8.1 節）。それでも DP の骨格は変わりません。

5. 表を埋める — もらう DP と配る DP

漸化式が決まったら表を埋めます。ループの書き方は 2 通りあります。

• もらう DP（pull）: dp[i] を、dp[i] に入ってくる遷移をすべて見て確定させる。「代入」で書けるので、初期化忘れに強い。
• 配る DP（push）: 確定した dp[i] から、出ていく遷移の先を更新する。

どちらでも答えは同じで、違うのは書きやすさです。「入ってくる辺」を列挙しやすいならもらう DP、「出ていく辺」を列挙しやすいなら配る DP を選ぶと素直に書けます。区間に一様に配るような遷移は、配る DP といもす法（差分配列）を組み合わせると書きやすくなります。

5.1 実装

// もらう DP（C++）
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n; cin >> n;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;
 
    const long long INF = 1e18;
    vector<long long> dp(n, INF);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1] + llabs(h[i] - h[i - 1]);
        if (i >= 2) dp[i] = min(dp[i], dp[i - 2] + llabs(h[i] - h[i - 2]));
    }
    cout << dp[n - 1] << '\n';
}

// 配る DP（C++）
vector<long long> dp(n, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
    if (dp[i] == INF) continue;              // 到達不能な状態からは配らない
    for (int d = 1; d <= 2 && i + d < n; d++) {
        long long cand = dp[i] + llabs(h[i + d] - h[i]);
        dp[i + d] = min(dp[i + d], cand);
    }
}

配る DP で if (dp[i] == INF) continue; を忘れると、INF + コスト を計算してしまいます。INF に LLONG_MAX のような «足したら壊れる値» を選んでいると、これがオーバーフローして負値になり、そのまま最小値として採用されます。INF は「加算しても壊れない値」にするのが定石です。long long なら 1e18、int なら 1'000'000'000 ではなく 1'000'000'000 / 2 程度を使い、加算の余地を残します。ただし、値が壊れない INF を選んでも、コストが負になりうる場合などは、到達不能な状態から配った値が INF を下回り、配った先が到達可能に見えてしまいます。ガードは必ず書いてください。

5.2 トップダウンかボトムアップか

どちらを使うかは、次の基準で選びます。

• 状態空間が疎（到達しない状態が大量にある、状態が文字列や集合で添字化しづらい）なら、メモ化再帰。
• 状態空間が密なら、あるいは定数倍や高速化テクニックを載せたいなら、ループ。
• 再帰の深さが $10^5$ を超えうるなら、ループ（あるいは明示的スタック）。Python はデフォルトの再帰上限が 1000 なので、sys.setrecursionlimit の引き上げに加えてスレッドスタックサイズの調整が必要になることもあります。

実務では、まずメモ化再帰で正しさを確認し、必要になったらループへ書き換えると進めやすくなります。漸化式が正しいと確認できていれば、ループへの変換は機械的な作業です。

6. 型のカタログ

この章は、典型的な DP の «型» を集めた辞書です。各節は単独で読めるので、必要な型だけ拾ってください。

型を覚えておくと、初見の問題で「これは区間をまとめる形だから、区間を状態にすればよさそうだ」と当たりをつけられます。当たりが外れたときは、3〜5 章の手順に戻ります。

6.1 ナップサック DP — 「疑似多項式」という言葉の意味

$N$ 個の品物があり、品物 $i$ は重さ $w_i$、価値 $v_i$ を持つ。重さの合計が容量 $W$ を超えないように品物を選ぶとき、価値の合計の最大値を求めよ。各品物は使うか使わないかの 2 択（0-1 ナップサック）とする。

品物を 1 つずつ見て、入れるか入れないかを決めます。全探索なら $2^N$ 通りの部分集合を試すことになります。先頭 $i$ 個の選び方のうち、この先に効くのは使った重さの合計だけです。どの品物をどう組み合わせて合計 $w$ になったかは、残りの選び方に影響しません。これで状態は «何個目まで見たか» と «使った重さ» の 2 次元に決まります。

dp[i][w] = 先頭 i 個から選び、重さの合計が w 以下のときの価値の最大値
dp[i][w] = max( dp[i-1][w] ,  dp[i-1][w - w_i] + v_i )
             ↑ i 番目を使わない   ↑ i 番目を使う（w >= w_i のときだけ）

「この先に効くのは使った重さ」と考えたときは «ちょうど $w$» が自然ですが、上では «$w$ 以下» と定義しています。重さが非負である以上、容量を余らせても損はしません。そのため «$w$ 以下» の表は、«ちょうど» の表について $w$ の小さいほうから累積最大値を取ったものにあたり、$w$ について単調非減少になります。

«ちょうど» では作れない重さのセルにも、«以下» の表ではより軽い組み合わせの最良値が入ります。最後に欲しいのは «$W$ 以下での最大» なので、この形にしておけば dp[N][W] を読むだけで答えになり、「ちょうど $W$ を使い切る組み合わせがない」場合の場合分けが要りません。

逆に «ちょうど» が必要な問題（6.2 節や部分和）では、到達不能なセルを明示的に区別します。最小化なら $\infty$、最大化なら $-\infty$、可否なら false です。

状態数 $N \times W$、遷移数 2 なので $O(NW)$ です。

0-1 ナップサック問題は NP 困難です。それでも $O(NW)$ の DP で解けるのは、$W$ が入力の値そのものであって、入力サイズ（ビット数）ではないからです。$W$ を二進表記したときの長さは $\log W$ なので、$O(NW)$ は入力サイズに対して指数的です。これを疑似多項式時間と呼びます。

「$W \le 10^5$ なら通るが、$W \le 10^9$ なら通らない」のはこのためで、実行時間は $W$ の値に比例して伸びます。

デモの 3 つのモードは、次の 3 通りの実装に対応しています。

2 次元表は定義どおりです。

// dp[i][w] = 先頭 i 個から選び、重さ合計 w 以下での最大価値
vector<vector<long long>> dp(n + 1, vector<long long>(W + 1, 0));
for (int i = 1; i <= n; i++)
    for (int w = 0; w <= W; w++) {
        dp[i][w] = dp[i - 1][w];
        if (w >= wt[i - 1])
            dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
    }

1 次元・逆順は、行 $i$ を計算するとき行 $i-1$ しか要らないことを使って次元を落とします。

vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; i++)
    for (int w = W; w >= wt[i]; w--)          // ← 降順が必須
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

1 次元・順方向にすると、dp[w - wt[i]] が「同じ品物ですでに更新済み」の値になり、同じ品物を何個でも使えることになります。0-1 ナップサックとしてはバグですが、個数無制限ナップサックの正しい実装になっています。デモでは、答えが 90 から 100 に変わります。ループの向き 1 つで、解いている問題が入れ替わるわけです。

// 個数無制限ナップサック：昇順ループが「正解」になる
for (int i = 0; i < n; i++)
    for (int w = wt[i]; w <= W; w++)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

個数制限つき（品物 $i$ を最大 $c_i$ 個まで使える版。上の 0-1 が $c_i = 1$、個数無制限が $c_i = \infty$ にあたります）は、素朴には $O(NWc)$ ですが、$c_i$ を $1, 2, 4, \dots$ と二進分割して 0-1 ナップサックに帰着すると $O(NW \log c)$、剰余類ごとにスライド最小値を使えば $O(NW)$ になります。

6.2 添字と値を入れ替える

同じナップサックでも、制約の形が変わると同じ状態設計が使えなくなります。EDPC E（Knapsack 2）は $N \le 100$、$W \le 10^9$、$v_i \le 10^3$ です。品物数は少ないのに容量だけが桁違いに大きく、$O(NW) = 10^{11}$ では間に合いません。

一方、価値の総和は高々 $N \times \max v_i = 100 \times 10^3 = 10^5$ です。そこで、大きすぎる «重さ» を添字から追い出し、代わりに小さい «価値» を添字にします。最適化する量と制約にする量を入れ替えるわけです。

これまで: dp[i][w] = 重さ w 以下での「価値の最大値」        ← 添字が重さ
入れ替え: dp[i][v] = 価値ちょうど v を作るための「重さの最小値」  ← 添字が価値

これで状態数は $N \times \sum v_i \le 100 \times 10^5 = 10^7$ となり、現実的になります。答えは dp[N][v] <= W を満たす最大の v です。

「片方の次元が大きすぎるなら、最適化対象と制約を入れ替えられないか」を疑う。これは DP における最も汎用的な発想転換です。

同じ発想が、3.2 節で定義した LIS の $O(n \log n)$ 解法にも現れます。

素朴な $O(n^2)$ 解法（3.2 節のもの）は dp[i] に長さを持ちました。高速版は逆に、長さを添字にし、値のほうを中身にします。

素朴: dp[i]    = 「a[i] で終わる増加列」の長さ          ← 添字が位置、中身が長さ
高速: tails[k] = 「長さ k+1 の増加列を作れる末尾」の最小値  ← 添字が長さ、中身が値

tails が常に狭義単調増加になるのが要点です（長い列の末尾は、短い列の末尾より小さくできないため）。ソート済みの配列なので二分探索が使え、要素 1 つあたり $O(\log n)$、全体で $O(n \log n)$ になります。

from bisect import bisect_left
 
def lis_length(a):
    tails = []
    for x in a:
        i = bisect_left(tails, x)     # 狭義単調増加。広義なら bisect_right
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

tails の長さは正しい答えですが、tails の中身は入力の部分列になっているとは限りません。デモの最後の tails = [1, 2, 5, 6] は、入力の並び順を満たしていません。列そのものを復元したいなら、各要素を挿入したときの位置と «そのとき 1 つ左のスロットを持っていた要素の添字» を記録する必要があります。

def lis_sequence(a):
    tails, tails_idx, parent = [], [], [-1] * len(a)
    for i, x in enumerate(a):
        k = bisect_left(tails, x)
        parent[i] = tails_idx[k - 1] if k > 0 else -1
        if k == len(tails):
            tails.append(x); tails_idx.append(i)
        else:
            tails[k] = x; tails_idx[k] = i
    res, cur = [], tails_idx[-1]
    while cur != -1:
        res.append(a[cur]); cur = parent[cur]
    return res[::-1]

6.3 格子 DP — diff と編集距離の骨格

2 本の列の接頭辞を 2 軸に取る DP は、実務で最も出番の多い型です。代表例は次の 2 問です。

最長共通部分列（Longest Common Subsequence, LCS）: 2 つの文字列 $s$, $t$ が与えられる。両方の部分列（連続でなくてよいが、順序は保つ）になっている文字列のうち、最も長いものを求めよ。例：$s =$ axyb、$t =$ abyxb なら axb や ayb が長さ 3 で最長。

編集距離（Levenshtein distance）: 文字列 $s$ に「1 文字の挿入・削除・置換」を繰り返して $t$ にするとき、必要な操作回数の最小値を求めよ。例：axyb → abyb（x を b に置換）→ abyxb（x を挿入）で 2 回。

どちらも「$s$ の先頭 $i$ 文字と $t$ の先頭 $j$ 文字」という接頭辞の組が状態になります。$s$ の $i$ 文字目と $t$ の $j$ 文字目をどう対応させるかを決めれば、残りは同じ形の小さい問題になるからです。状態数 $nm$、遷移数 2〜3 で $O(nm)$ です。

同じ表・同じ走査順で、境界の値と遷移の定義を差し替えると別の問題になります。

# 最長共通部分列（境界: dp[i][0] = dp[0][j] = 0）
if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
# 編集距離（Levenshtein。境界: dp[i][0] = i, dp[0][j] = j）
if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1]
else:                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

この格子は、次のような応用の土台になっています。

• diff: LCS に入らなかった文字が、削除・追加として表示されます。GNU diff や git のデフォルトは Myers のアルゴリズム（1986）です。編集グラフ上の最短経路を $O(ND)$（$N$ は 2 つの列の長さの合計、$D$ は差分の大きさ）で求めるので、差分が小さいほど速くなります。
• スペル訂正・あいまい検索: 編集距離そのもの。閾値 $k$ 付きなら対角帯だけ計算して $O(nk)$ に落とせます。
• バイオインフォマティクス: Needleman–Wunsch（1970、大域アライメント）と Smith–Waterman（1981、局所アライメント）は、この格子にギャップペナルティーと置換スコア行列を入れたものです。
• DTW（動的時間伸縮）: 時系列の対応付け。遷移の定義を変えた同じ格子です。

長さだけが欲しいなら、2 行のローリング配列でメモリーを $O(\min(n,m))$ に減らせます。列そのものが欲しい場合も、Hirschberg のアルゴリズム（1975）で分割統治を組み合わせれば、時間 $O(nm)$ のまま空間 $O(\min(n,m))$ で復元できます。

下界の結果もあります。Backurs と Indyk（2015）は、SETH（強指数時間仮説）が真なら、任意の $\delta > 0$ について編集距離を $O(n^{2-\delta})$ 時間で計算できないことを示しました。LCS についても同様の結果があります。したがってこの $O(nm)$ に対しては、語長や対数の因子を削る工夫（ビット並列化、Four Russians 法）を除けば、本質的な改善は期待できません。

6.4 区間 DP

「隣り合うものをくっつけていく」構造の問題は、区間を状態にします。代表例は次の 2 問です。

スライム合体（EDPC N）: $N$ 個のスライムが一列に並び、$i$ 番目の大きさは $a_i$。隣り合う 2 匹を合体させると、大きさは和になり、そのとき 2 匹の大きさの和に等しいコストがかかる。全部を 1 匹にするまでの総コストの最小値を求めよ。

行列連鎖積: $A_1 A_2 \cdots A_n$ を掛けるとき、掛ける順序（括弧の付け方）によってスカラー乗算の回数が変わる。回数を最小化する括弧の付け方を求めよ。

どちらも、最後に「区間 $[l, r)$ 全体が 1 つにまとまる」瞬間があり、その直前には必ずある分割点 $k$ で左右に分かれていたはずです。この $k$ を全通り試すのが遷移になります。「先頭から順に決める」線形 DP と違い、決める順番が «区間の大きさ» になっているのがこの型の特徴です。

dp[l][r] = 区間 [l, r) をひとつにまとめるときの最適値
dp[l][r] = min over k in (l, r) of  dp[l][k] + dp[k][r] + cost(l, r)

状態数 $O(n^2)$、遷移数 $O(n)$ で $O(n^3)$ です。ループは区間の長さが短いほうから回します（長い区間は短い区間の答えに依存するため、これがトポロジカル順序になります）。上の骨格は cost(l, r) を min の外に置いた形（EDPC N や最適二分探索木がこちら）ですが、行列連鎖積のようにコストが分割点に依存する場合は dp[l][k] + dp[k][r] + p_l p_k p_r のように min の内側に入ります。

コスト関数 $w$ が、次の四角不等式（quadrangle inequality）を満たすとします。

さらに、区間の包含に関する単調性 $w(b, c) \le w(a, d)$（同じく $a \le b \le c \le d$）も満たすなら、最適分割点は単調になります。直観的には「区間を右に広げると最適な分割点も右にしか動かない、左に広げると左にしか動かない」ということで、この 2 つの向きがそれぞれ探索範囲の下限と上限を与えます。

そのため、$dp[l][r]$ の分割点を探す範囲を $[\,\text{argmin}(l, r-1),\ \text{argmin}(l+1, r)\,]$ に限定できます。区間の長さを固定すると、探索範囲の幅の合計は隣どうしで打ち消し合って $O(n)$ に収まるので、全体では $O(n^2)$ に落ちます（Knuth–Yao 高速化）。Knuth が 1971 年に最適二分探索木（各キーの検索頻度が分かっているとき、平均検索コストを最小にする二分探索木を作る問題）で示し、Yao が 1980 年に一般化した結果です。

// 区間 DP の骨格（もらう DP）
for (int len = 2; len <= n; len++)
    for (int l = 0; l + len <= n; l++) {
        int r = l + len;
        for (int k = l + 1; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r]);
        dp[l][r] += cost(l, r);
    }

6.5 木 DP と全方位木 DP

木の上では、部分木が自然な部分問題になります。例として次の問題を扱います。

木の最大重み独立集合: 頂点に重み $w_v$ を持つ木が与えられる。辺で直接つながった 2 頂点を同時には選ばないという条件のもとで、選んだ頂点の重みの合計を最大化せよ。

一列に並んだ場合（＝パス）なら「$i$ 番目を使うか使わないか」の線形 DP ですが、木では子が複数あります。それでも構造は同じで、頂点 $v$ の部分木の答えは、子たちの部分木の答えから決まります。ただし「$v$ 自身を選んだかどうか」で子の自由度が変わるので、その 1 ビットを状態に足します。

# 木の最大重み独立集合
# 戻り値 (take, skip) = (v を選ぶ場合の部分木の最大値, v を選ばない場合の最大値)
def dfs(v, parent):
    take, skip = w[v], 0
    for c in graph[v]:
        if c == parent: continue
        t, s = dfs(c, v)
        take += s          # v を使うなら子は使えない
        skip += max(t, s)  # v を使わないなら子は自由
    return take, skip
 
answer = max(dfs(root, -1))

状態は「頂点 $v$」×「$v$ 自身を選んだか」の 2 次元です。計算量は各辺を 1 回ずつ見るので $O(n)$。EDPC P（Independent Set）は同じ状態のまま $(\max, +)$ を $(+, \times)$ に取り替えた数え上げ版で、max を足し算に、足し算を掛け算にすると独立集合の個数になります。4.2 節の半環の話がそのまま効く例です。

全方位木 DP（rerooting）は、「すべての頂点それぞれを根としたときの答え」をまとめて $O(n)$ で求める技法です。上の DFS は根を 1 つ決めたときの答えしか出しません。素朴に $n$ 回やり直すと $O(n^2)$ ですが、各頂点について、子の側の答え（1 回目の DFS で葉から集める）と親の側の答え（2 回目の DFS で根から配る）を組み合わせると、2 回の DFS で済みます。鍵は、«1 つの子を除いた残りの子すべての集約» を左右からの累積で求め、頂点あたり $O(\deg v)$ に抑えることです。EDPC V がこの典型です。

6.6 bit DP — 順列を集合に畳む

順序が本質的に効く問題でも、「これまでに何をしたか」が集合として要約できるなら、状態を $2^n$ に畳めます。題材は巡回セールスマン問題です。

巡回セールスマン問題（Travelling Salesman Problem, TSP）: $n$ 個の都市と、都市 $u$ から $v$ への移動距離 $D[u][v]$ が与えられる。都市 0 から出発してすべての都市をちょうど 1 回ずつ訪問し、都市 0 に戻る巡回路のうち、総距離が最小のものを求めよ。

素朴に解くと、都市 0 以外の $n-1$ 都市の並べ方 $(n-1)!$ 通りを試すことになります。しかし、「どの都市を訪問済みか」と「いまどこにいるか」が同じなら、この先の最適な回り方は同じです。「$0 \to 1 \to 2 \to 3$ と回った」のと「$0 \to 2 \to 1 \to 3$ と回った」を比べると、訪問済み集合はどちらも $\lbrace 0,1,2,3 \rbrace$、現在地はどちらも都市 3 なので、残りの都市の回り方に違いは出ません。距離が非対称（$D[u][v] \neq D[v][u]$）でも同じです。2 つの経路で違うのはここまでに払ったコストだけで、この先に残っている仕事は同一だからです。したがって、訪問順そのものは覚えなくて構いません。

訪問済み集合は $n$ ビットの整数 $S$ で表します（$i$ ビット目が 1 なら都市 $i$ を訪問済み）。集合をビット列に押し込めるので、この型を状態圧縮 / bit DP と呼びます。$dp[S][v]$ を「都市 0 を出発して集合 $S$ の都市をちょうど 1 回ずつ訪れ、いま都市 $v$ にいるときの最小コスト」とすると、漸化式は次のようになります。

状態数 $2^n \cdot n$、遷移数 $n$ で $O(2^n n^2)$。Held と Karp（1962）、および Bellman（1962）が独立に与えた結果です。指数は消えませんが、階乗は消えます。$n = 20$ なら $(n-1)! \approx 1.2 \times 10^{17}$ に対して $2^n n^2 \approx 4.2 \times 10^8$ で、後者は現実的な範囲に入ります。

// Held–Karp
vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
dp[1][0] = 0;
for (int S = 1; S < (1 << n); S++) {
    if (!(S & 1)) continue;
    for (int v = 0; v < n; v++) {
        if (!((S >> v) & 1) || dp[S][v] == INF) continue;
        for (int u = 0; u < n; u++) {
            if ((S >> u) & 1) continue;
            int T = S | (1 << u);
            dp[T][u] = min(dp[T][u], dp[S][v] + D[v][u]);
        }
    }
}

bit DP の実装でよく使うイディオムは次のとおりです。

__builtin_popcount(S)          // 立っているビット数
S & (S - 1)                    // 最下位の 1 を落とす
S & -S                         // 最下位の 1 だけを取り出す
for (int T = S; T; T = (T - 1) & S)   // S の空でない部分集合を全列挙

最後のイディオムで全 $S$ について部分集合を回すと $O(3^n)$ になります（各要素が「$T$ に入る / $S \setminus T$ に入る / $S$ に入らない」の 3 通りだから）。部分集合の総和だけが必要なら、SOS DP（高速ゼータ変換）で $O(2^n n)$ に落とせます。

// f[S] を「S の部分集合すべてにわたる総和」に書き換える
for (int i = 0; i < n; i++)
    for (int S = 0; S < (1 << n); S++)
        if ((S >> i) & 1) f[S] += f[S ^ (1 << i)];

6.7 桁 DP

「$A$ 以上 $B$ 以下の整数のうち、ある条件（各桁の和が $D$ の倍数、など）を満たすものはいくつあるか」

$B$ が $10^{18}$ でも、1 つずつ数える代わりに桁を上位から 1 桁ずつ決めることで数えられます。

このとき問題になるのが「上限 $B$ を超えないこと」で、これをいま作りかけの数が $B$ の接頭辞と完全に一致しているか（tight）という 1 ビットで表します。tight なら次の桁は $B$ のその桁までしか置けず、tight でない（すでに $B$ より小さいことが確定している）なら 0〜9 が自由に置けます。

from functools import cache
 
def count_upto(n_str, ...):
    L = len(n_str)
 
    @cache
    def rec(pos, tight, started, state):
        if pos == L:
            return 1 if is_ok(state) else 0
        limit = int(n_str[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            total += rec(
                pos + 1,
                tight and d == limit,     # 上限に張り付いたままか
                started or d > 0,         # 先頭ゼロを抜けたか
                next_state(state, d, started or d > 0),
            )
        return total
 
    return rec(0, True, False, initial_state)
 
# 区間は差で取る
answer = count_upto(str(B)) - count_upto(str(A - 1))

started（先頭ゼロの扱い）を忘れると、「桁の中に 0 がいくつあるか」のような条件で必ずずれます。tight と started の 2 つのフラグは桁 DP の定型で、tight はほぼすべての問題で、started は先頭のゼロが条件に影響する問題で必要になります。

6.8 確率・期待値 DP

「最適化」ではなく「平均」を求める DP です。例として次の問題を考えます。

$N$ 枚の皿があり、皿 $i$ には寿司が $a_i$ 貫（$1 \le a_i \le 3$）のっている。「$N$ 枚から等確率で 1 枚選び、寿司が残っていれば 1 貫食べる（空なら何もしないが、操作は 1 回と数える）」を繰り返すとき、全部の寿司がなくなるまでの操作回数の期待値を求めよ。（EDPC J: Sushi）

確率 DP は 4.2 節でいう $(+, \times)$ 半環の DP です。期待値 DP には固有の注意点が 2 つあります。

1 つ目：向きを逆に取る。「状態 $s$ から終端までにかかる操作回数の期待値」を dp[s] に持ち、終端側から埋めます。「始点から $s$ までの期待値」では、期待値の線形性を使った合成ができません。

2 つ目：自己ループは方程式を解く。「確率 $p$ で何も起きず同じ状態に留まる」場合、

と移項して解きます。同じ状態に何度も戻る分を無限級数で足し合わせなくても、閉じた形で求まります。$p = 1$（絶対に抜けられない）のときは期待値が発散するので、問題側でそれが起きないことを確認してください。

EDPC J（Sushi）では、$a_i \le 3$ という制約のおかげで «寿司が 1 貫の皿の数、2 貫の皿の数、3 貫の皿の数» の 3 次元を状態に取れます。空の皿を選ぶと同じ状態に留まるので、上の自己ループの処理が必要になる典型例です。

6.9 部分和と bitset — 「作れるか」だけなら定数倍で高速化できる

3.5 節の定石 (d) の具体例です。「重さの部分集合で和 $j$ をちょうど作れるか」だけを問う部分和問題は、dp[j] が bool になります。

dp[j] = 和 j が作れるか（bool）
品物 w を追加：dp_new = dp OR (dp << w)

dp をビット列とみなすと、遷移がシフトと論理和 1 回になります。C++ なら std::bitset で $O(nW/64)$、つまり素朴な $O(nW)$ の 64 分の 1 です。

bitset<100001> dp;
dp[0] = 1;
for (int w : weights) dp |= dp << w;   // dp[j] が立っていれば和 j を作れる

Python では、任意精度整数をそのままビット集合として使えます。ループ回数が減るぶん、素朴なリスト DP より 1〜2 桁速くなることも珍しくありません。

dp = 1                       # 第 0 ビットだけ立っている = 和 0 は作れる
for w in weights:
    dp |= dp << w
can_make = lambda j: (dp >> j) & 1

ただし、この形では復元も、選ぶ個数の制限もできません。「どれを選んだか」が必要なら bool ではなく親を持つ表に戻す必要があります。定数倍の高速化は、たいてい情報を捨てることと引き換えです。

7. 遷移を速くする

状態数は減らせないが遷移が重い、という状況はよく起きます。どの道具が使えるかは、遷移の形で決まります。

7.1 累積和：最も費用対効果が高い

dp[i] = sum(dp[j] for j in [i-k, i-1]) のように遷移が区間の総和なら、累積和で $O(k)$ が $O(1)$ になります。

# dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]
S = [0] * (n + 2)          # dp の累積和
dp[0] = 1; S[1] = 1
for i in range(1, n + 1):
    lo = max(0, i - k)
    dp[i] = (S[i] - S[lo]) % MOD
    S[i + 1] = (S[i] + dp[i]) % MOD

配る DP 側で「区間に一様に加算する」なら、いもす法（差分配列）で同じ効果が得られます。EDPC M（Candies）や T（Permutation）がこの型です。

7.2 スライド最小値

dp[i] = min(dp[j] for j in [i-k, i-1]) + c[i] のように窓の最小値を取るなら、単調両端キュー（monotonic deque）で償却 $O(1)$ になります。

from collections import deque
 
dq = deque()               # (index, value) を value 昇順で保持
for i in range(n):
    while dq and dq[0][0] < i - k:      # 窓から出た要素を捨てる
        dq.popleft()
    dp[i] = c[i] + (dq[0][1] if dq else 0)
    while dq and dq[-1][1] >= dp[i]:    # 自分より大きい末尾は将来使われない
        dq.pop()
    dq.append((i, dp[i]))

単調両端キューが正しく動くのは、「自分より大きくて自分より古い要素は、二度と最小値にならない」という性質があるからです。個数制限つきナップサックの $O(NW)$ 解法も、剰余類ごとにこの構造を使います。

7.3 Convex Hull Trick

$dp[i] = \min_j (dp[j] + a_j \cdot x_i)$ の形、つまり直線の族の下側包絡線を評価する遷移では、傾きと問い合わせが単調なら $O(n)$、そうでなくても Li Chao 木で $O(n \log n)$ になります。

最小構成の練習問題が EDPC Z（Frog 3）です。Frog 1 と同じ設定で、ジャンプ先が 1〜2 個先ではなく «自分より先のどの石でもよい» になり、石 $j$ から石 $i$ へのコストが $(h_i - h_j)^2 + C$ になります。素朴に書くと遷移が $O(n)$ で全体 $O(n^2)$ です。ここで $dp[i] = \min_j (dp[j] + (h_i - h_j)^2 + C)$ を展開すると

となり、$j$ ごとに «傾き $-2h_j$、切片 $dp[j] + h_j^2$ の直線» が 1 本対応します。求めたいのは、$x = h_i$ での直線の族の最小値、すなわち下側包絡線の値です。「$i$ に依存する部分と $j$ に依存する部分に分離できるか」が、この変形の適用可否を判断する基準です。

EDPC Z では $h_1 < h_2 < \dots < h_N$ という制約があり、これが効きます。追加していく直線の傾き $-2h_j$ は単調減少で、問い合わせる $x$（$= h_i$）は単調増加。最小値を取るときは «$x$ が大きいほど最適な直線の傾きは小さい» ので、この 2 つの単調性が揃えば包絡線を傾きについて単調な両端キューで管理でき、償却 $O(n)$ で済みます（7.2 節のスライド最小値と同じく両端キューを使いますが、不変条件が違います。こちらは «末尾の直線が不要になったら pop、先頭の直線が最適でなくなったら pop»）。単調性がない一般の場合は Li Chao 木（$x$ の定義域をセグメント木状に分割し、各ノードに «その区間で最も優勢な直線» を 1 本だけ持つデータ構造）などが必要で、$O(n \log n)$ になります。EDPC Z では、この高速化が使えるかどうかを問題の制約が決めています。

7.4 行列累乗

線形漸化式で $n$ が $10^9$ 級なら、遷移を行列にして累乗します。

状態数 $k$ に対して $O(k^3 \log n)$。グラフの隣接行列の $n$ 乗が「長さ $n$ の経路数」になるのも同じ原理で（$(+, \times)$ 半環）、EDPC R（Walk）がこの経路数え上げ版です。$(\min, +)$ 半環で同じことをすると「辺をちょうど $n$ 本使う最短経路」になります。

7.5 どれを使うかの判断

高速化テクニックは、名前を知っているだけでは使えません。遷移の形を見て、適用条件を満たすかを確認します。確認する順番は次のとおりです。

1. まず状態が減らせないかを疑う。次元を 1 つ落とせるなら、どんな定数倍改善よりも効く。
2. 遷移が区間の集約なら累積和・いもす法・セグメント木。
3. 遷移が窓の min/max ならスライド最小値。
4. 遷移が直線の族なら Convex Hull Trick / Li Chao 木。
5. 遷移が分割点の探索で、コストが四角不等式を満たすなら（6.4 節）Knuth–Yao / 分割統治最適化。

8. 実装の作法

8.1 初期値・到達不能・オーバーフロー

• 最小化なら INF、最大化なら -INF で初期化し、「到達不能」と「値が 0」を区別する。数え上げなら 0 初期化。
• INF は加算しても壊れない値にする（long long なら 1e18。int で 1e9 は危険）。
• 配る DP では if (dp[i] == INF) continue; を必ず書く。
• 数え上げでは毎回 $\bmod$ を取る。$10^9+7$ と $998244353$ が定番で、後者は NTT（数論変換）に適した素数（$998244353 = 119 \cdot 2^{23} + 1$）なので、畳み込みを使う問題で選ばれる。

8.2 復元

競技プログラミングの多くの問題は「最適値」だけを聞いてきますが、実務では「最適解そのもの」が必要になるのが普通です。方法は 2 つあります。

親を記録する: from[state] に遷移元を保存し、終端からたどります。実装は単純ですが、状態数と同じだけメモリーを食います。

再計算する: 表さえ残っていれば、終端から «どの遷移がその値を作ったか» を再判定できます。ナップサックのデモで使っているのがこれです。追加メモリーが不要な代わりに、条件式を漸化式と二重に書くことになり、片方だけ変更すると両者が食い違います。

// 追加メモリなしの復元（0-1 ナップサック）
vector<int> chosen;
int w = W;
for (int i = n; i >= 1; i--) {
    if (dp[i][w] != dp[i - 1][w]) {   // 値が変わった = 品物 i を使った
        chosen.push_back(i - 1);
        w -= wt[i - 1];
    }
}

ローリング配列で次元を落とすと、この «真上と比べる» 復元ができなくなります。復元が必要なら、次元圧縮は諦めるか、Hirschberg 型の分割統治を使います。どちらを取るかは、設計の段階で決めておいてください。

8.3 メモリーとキャッシュ

$O(NW)$ の表は、$N = 10^2$、$W = 10^5$、long long で 80 MB です。ローリング配列にすれば 800 KB になります。競技プログラミングでよくあるメモリー制限（256 MB 前後）では、2 次元表がそのままでは載らない場面が実際に起きます。

もう 1 つ効くのがアクセス順序です。dp[i][w] を行優先（w を内側ループ）で走査すればキャッシュに乗りますが、列優先にすると同じ計算量でも数倍遅くなることがあります。多次元配列は「最も内側のループが最も右の添字を動かす」形に揃えるのが基本です。

8.4 デバッグ：ストレステスト

DP のバグは「サンプルは通るが WA（不正解）」の形で出ることが多いです。最も効率が良いデバッグは、小さいランダムケースで全探索と突き合わせることです。

import random
 
def brute(items, W):
    best = 0
    for mask in range(1 << len(items)):
        w = v = 0
        for i, (wi, vi) in enumerate(items):
            if mask >> i & 1:
                w += wi; v += vi
        if w <= W:
            best = max(best, v)
    return best
 
for trial in range(10_000):
    n = random.randint(1, 8)
    W = random.randint(1, 15)
    items = [(random.randint(1, 8), random.randint(1, 20)) for _ in range(n)]
    if (expected := brute(items, W)) != (got := knapsack_dp(items, W)):
        print("MISMATCH", items, W, expected, got)
        break

このループを回すと、境界条件（$w = 0$、品物 0 個、重さが容量ちょうど）のバグが数秒で見つかります。全探索の実装は捨てずに取っておきましょう。DP の出発点が全探索なので、手元にすでにあるはずです。

もう 1 つ有効なのが、表そのものを出力することです。小さいケースで表を印字して手計算と突き合わせれば、「初期化がおかしい」のか「遷移がおかしい」のかをすぐに切り分けられます。

8.5 症状から原因を引く表

DP の不具合は、症状と原因の対応がかなり定型的です。提出結果が合わないときは、次の表で疑う箇所を絞れます。

とくに «数え上げの重複» は、最適化 DP では起きないのに数え上げ DP では頻発します。「同じ集合を、選ぶ順番を変えて 2 回数えていないか」を必ず確認してください。品物ループを外側、容量ループを内側にする順序が 0-1 ナップサックで重要なのも、根は同じ話です。

8.6 スクリプト言語で書くときの現実

Python でそのまま DP を書くと、$10^7$ 回の遷移でも数十秒かかることがあります。実務でも競技でも使える対処は次のとおりです。

• メモ化のキーを整数に潰す。 (i, w) のタプルより i * (W + 1) + w のほうが辞書引きが軽く、そもそもリストで持てるならリストにします。
• ボトムアップにして関数呼び出しを消す。目安として、再帰 1 回のコストはループ 1 周の数倍から数十倍です。
• ベクトル化する。ナップサックの 1 行更新はスライス演算 1 回で書けます。逆順ループをスライスに置き換えても、右辺が先に評価されて一時配列になるため 0-1 の意味は保たれます。

import numpy as np
 
def knapsack(items, W):
    dp = np.zeros(W + 1, dtype=np.int64)
    for w, v in items:
        # dp[w:] = max(dp[w:], dp[:-w] + v) と同じ。右辺は先に一時配列になる
        np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])
    return int(dp[W])

• bool の DP は整数のビット演算にする。 6.9 節のとおりです。
• PyPy が使えるなら使う。素朴なループ主体の DP では、CPython の 10 倍以上速くなることがあります。

9. 実務のなかの DP

DP は競技プログラミングの外でも広く使われています。DP だと意識されないまま使われている例も少なくありません。

9.1 テキスト差分（diff）

git diff の既定アルゴリズムは Myers（1986）です。これは編集グラフ上で「削除と挿入の合計 $D$ が最小の経路」を求める DP で、$O(ND)$ 時間で動きます。差分が小さいときは $O(nm)$ よりずっと速いため、バージョン管理の標準になっています。git diff --histogram や --patience は、可読性の高い差分を得るための別のヒューリスティクスです。

9.2 形態素解析

日本語の形態素解析器（MeCab、Kuromoji など）は、入力文からラティス（単語候補のグラフ）を作り、その上で最小コスト経路を Viterbi アルゴリズムで求めます。「単語の生起コスト + 品詞の連接コスト」の総和を最小化する経路が解析結果です。これは $(\min, +)$ 半環上の DAG 最短経路で、2 章の Frog 1 と同じ構造です。

9.3 データベースの結合順序最適化

$n$ 個のテーブルを結合するとき、結合順序は左深木（left-deep tree）に限っても $n!$ 通りあります。System R（Selinger ら、1979）は、部分集合ごとに最良のプランを 1 つだけ持つ DP を導入しました。状態は「結合済みテーブルの集合」で、これは bit DP です。TSP と同じ構造なので、テーブル数が増えると急に効かなくなります。たとえば PostgreSQL は既定で、結合する FROM 項目が 12 個以上になると遺伝的アルゴリズムによる GEQO に切り替えます（geqo_threshold）。詳細は SQL はどうやってディスク上のバイト列に届くのか で扱っています。

9.4 組版

TeX の段落分割（Knuth–Plass、1981）は、行末の候補すべてを状態とする DP です。1 行ずつ貪欲に「入るだけ詰める」方式とは違い、段落全体の «見た目の悪さ» の総和を最小化します。単語間の空白の伸縮に対するペナルティーを定義し、段落全体を最短経路問題として解きます。

9.5 画像処理

Seam carving（Avidan と Shamir、2007）は、画像を «縦につながった 1 画素幅の経路» 単位で削ることで、被写体を歪めずにリサイズします。この «継ぎ目» は、エネルギー関数の最小経路を格子上の DP で求めたものです。

9.6 強化学習と最適制御

強化学習の価値反復（value iteration）は Bellman 方程式

を不動点まで反復するアルゴリズムです。この記事で扱ってきた DP との違いは依存関係に閉路があることです。そのため 1 回のトポロジカル順の走査では終わらず、割引率 $\gamma < 1$ による縮小写像の性質を使って収束させます。

9.7 実務で DP を使うときの現実的な注意

• 使えるかどうかは結局、状態数で決まる。実務の問題は状態が爆発しがちで、そのままでは載りません。状態を粗く近似する（離散化、特徴量への射影）、ビーム幅で刈る、上位 $k$ 件だけ持つ、といった «正確さを捨てる» 判断が必要になります。
• 疑似多項式性の罠。「重さを 0.01 単位で扱う」と決めた瞬間に $W$ が 100 倍になります。単位の設計が計算量を決めます。
• DP は入力の変化に弱い。入力が少し変わるたびに表全体を作り直す設計は、オンライン処理では破綻します。差分更新できる構造（セグメント木上の DP、遷移行列の再利用）を検討してください。

10. DP が向かないとき

• 状態が定義できない: 「これまでの履歴すべて」が将来に影響するなら、要約が作れません。この場合は探索 + 枝刈り、あるいはヒューリスティクスへ。
• 状態数が爆発する: $2^n$ は $n = 20$ 前後が限界です。分枝限定法、A*、ビームサーチ、あるいは近似アルゴリズムを検討します。0-1 ナップサックには FPTAS（任意の $\varepsilon > 0$ に対し、最適値の $1 - \varepsilon$ 倍以上の解を、入力サイズと $1/\varepsilon$ の両方について多項式の時間で返す枠組み）が存在します。
• 連続状態: 状態が実数値なら表に載りません。離散化するか、価値関数を関数近似する（近似動的計画法、強化学習）方向になります。
• 制約が «全体» に効く: 「選んだ要素の分散が閾値以下」のような、部分和に分解できない制約は状態に落としづらいです。ラグランジュ緩和（Alien's trick はその一種）で扱える場合があります。

11. 練習の順序

型を身につけるには、分類された問題集を順に解くのが効率的です。AtCoder の Educational DP Contest は A から Z まで 26 問が «型» ごとに並んでおり、この記事の各節とほぼ 1 対 1 に対応します。

解くときは、いきなり漸化式を書かず、必ず全探索から始めてください。「全探索を書く → 引数を見る → 状態を決める → 計算量を掛け算する」という手順を毎回踏むことが、初見の問題に対応するいちばん確実な訓練になります。

まとめ

• DP は覚える漸化式の集合ではなく、全探索を «状態» で圧縮する設計手順である。
• 状態とは「この先の最適な決め方に影響する情報だけを残した要約」。遷移が書けないなら状態が足りていない。
• 計算量は状態数 × 遷移数。実装前に必ず暗算する。
• DP は DAG 上の最短経路であり、評価順序はトポロジカル順序である。閉路がある場合は層を足すか、順序を貪欲に確定させるか、反復で不動点に落とす。
• 半環を差し替えれば、最小化・最大化・数え上げ・確率が同じ骨格で書ける。
• 高速化できるかどうかは遷移の形で判定する。その前に、状態を減らせないかを疑う。
• diff、形態素解析、クエリー最適化、組版、強化学習で使われる DP も、競技プログラミングで書く表と同じ構造をしている。