情報管理技術士 学習ノート
← 一覧へ
コンピューティング・組込み
#동적계획법#최적부분구조#중복부분문제#메모이제이션#점화식
最終更新 · 2026-11-03

動的計画法(Dynamic Programming)

1. 概要

A. 定義

動的計画法(Dynamic Programming, DP) とは、一つの大きな問題を互いに重なり合う小さな部分問題に分解し、各部分問題の解を一度だけ計算して保存(記憶)したうえで再利用することにより、指数的探索を多項式時間へ引き下げる最適化アルゴリズム設計技法である。

動的計画法は1950年代にリチャード・ベルマン(Richard Bellman)が多段階意思決定問題を解くために確立した技法であり、名称の「dynamic」は時間に沿った多段階決定を、「programming」は数学的最適化(計画法)を意味する。今日DPはアルゴリズム設計の三大パラダイム(分割統治・貪欲・動的計画法)の一つであり、「同じ部分問題を何度も繰り返し解く」非効率を除去する中核的な道具として定着している。

B. 登場背景と必要性

多くの最適化問題は、単純な再帰(全探索)で定義すると、同一の部分問題を指数的に重複計算する。最もよくある例がフィボナッチ数列である。fib(n) = fib(n-1) + fib(n-2)をそのまま再帰呼び出しすると、fib(n-2)は二度、fib(n-3)は三度計算され、全体の呼び出し数は黄金比に比例して約O(1.618ⁿ)へ急増する。n=50になっただけでも呼び出しが数億回に達し、実用時間内に終わらない。問題の「解」は明らかに多項式個であるのに、探索方式が指数的であるという矛盾こそが、DPが解決しようとする点である。

動的計画法はこの重複を「一度計算した答えを保存し、再び必要になれば取り出して使う」という単純だが強力な原理で除去する。フィボナッチの相異なる部分問題はfib(0)~fib(n)のn+1個のみであるため、各々を一度ずつだけ計算すれば全体はO(n)で終わる。すなわちDPの本質は、時間をメモリと交換(空間・時間トレードオフ) し、重複計算という指数的浪費を多項式の保存空間へ吸収することである。この交換が成り立つには、問題が二つの条件を満たさねばならない。

DPの必要性は、「多項式個の解を指数的に探索する」あらゆる最適化問題で繰り返し現れる。経路探索、資源配分、文字列整列、日程計画など、一見無関係に見える問題が、実は「小さな決定が累積して最適な全体決定をなす」という共通構造を持ち、全探索では決定の組合せが指数的に急増する。DPはこの急増を「状態」という中間要約へ畳み込み、同じ状態に到達する無数の経路を一つの保存値で代表させる。したがってDPを身につけることは、個々の問題の解法を暗記することではなく、この共通構造を見抜いて状態へ抽象化する眼を養うことである。

C. DPが成り立つ二つの条件

DPはどんな問題にでも適用できるわけではない。適用可能性は 最適部分構造(Optimal Substructure) と 重複部分問題(Overlapping Subproblems) という二つの条件で判別する。前者は「大きな問題の最適解が小さな問題の最適解で構成される」性質であり、後者は「同じ小さな問題が繰り返し現れる」性質である。二つの条件は独立であるため、両方を満たせばDPが、最適部分構造のみあり重複がなければ分割統治が、さらに局所最適が全体最適を保証すれば貪欲法が適する。この判別は後の比較節で詳しく扱う。

二つの条件は、DPの「適用可否」だけでなく「効率」まで併せて説明する。最適部分構造が漸化式の「正確性」(部分解を結合して正しい全体解が出るか)を保証するなら、重複部分問題はDPの「利得」(保存・再利用でどれだけ節約するか)を決定する。重複がほとんどなければ保存コストが増えるだけで利得がなく、事実上分割統治と変わらず、重複が多いほど指数から多項式への削減幅が大きくなる。したがって、問題を受け取ったら二つの条件を各々明示的に確認する習慣が、誤った適用と不要な適用をともに濾し取る最初の関門となる。

2. 動的計画法の原理と構造

動的計画法の全体構造は「問題分解 → 状態定義 → 漸化式 → 保存・再利用 → 解復元」の流れとして理解できる。以下の構造図は、全探索(重複計算)とDP(保存・再利用)の違いを一目で示す。

flowchart TB
  P["元の問題"] --> SUB["部分問題へ分解"]
  SUB --> CHK{"既に計算した<br/>部分問題か?"}
  CHK -->|"はい(重複)"| MEM["保存領域から照会(O(1))"]
  CHK -->|"いいえ(初回)"| CALC["漸化式で計算"]
  CALC --> STORE["保存領域へ記録(メモ化)"]
  STORE --> COMB["上位問題の解へ結合"]
  MEM --> COMB
  COMB --> ANS["元の問題の最適解"]

A. 最適部分構造(Optimal Substructure)

最適部分構造とは、全体問題の最適解がその部分問題の最適解のみで構成される性質である。例えばソウル→釜山の最短経路がソウル→大田→釜山を通るなら、その経路に含まれるソウル→大田区間もまたソウル→大田の最短経路でなければならない。もしより短いソウル→大田経路があれば全体経路もより短くなりうるため、「最適」という仮定に矛盾するからである。この性質のおかげで、大きな問題を小さな問題の答えで「漸化式(recurrence relation)」の形に表現できる。

最適部分構造が重要である理由は、これがなければ小さな問題の答えをいくら保存しても大きな問題を構成できないからである。例えば「最長単純経路(longest simple path)」問題は最適部分構造が成り立たない。二つの部分経路を繋ぐと頂点が重複し「単純経路」という制約が崩れうるため、部分最適解の結合が全体最適解を保証しない。このようにDP適用前には必ず「部分解の結合が全体解をなすか」をまず検証せねばならない。

B. 重複部分問題(Overlapping Subproblems)

重複部分問題とは、再帰的に問題を解くとき同一の部分問題が何度も繰り返し呼び出される性質である。フィボナッチでfib(3)が数回再計算されるのが典型例である。この重複が多いほどDPの利得が大きくなる。逆に併合ソートのように部分問題が互いに重ならず毎回新しい入力を扱えば、保存して再利用するものがないため、DPではなく分割統治が正しい。

重複部分問題は「相異なる部分問題の総数」で定量化される。フィボナッチはn+1個、0/1ナップサック問題は(物品数)×(容量)個、最長共通部分列(LCS)は(文字列1の長さ)×(文字列2の長さ)個の相異なる部分問題を持つ。DPの時間複雑度はおおむね「相異なる部分問題数 × 部分問題一つを解く費用」で計算されるため、状態空間の大きさを正確に把握することが性能分析の出発点である。

この定量化は実務で、コーディング前に「DPは果たして動くのか」を判断する根拠となる。例えば状態が(物品1,000個)×(容量100万)なら状態数が10億に達し、メモリ・時間ともに限界を超えるため、DPをそのまま適用する前に状態縮約や近似アルゴリズムを検討すべきという信号となる。逆に状態数が数百万以内なら安心してDPを設計できる。このように「状態空間の大きさ推定」は、DP適用の妥当性を先行検証する実務的チェックポイントである。

C. 二つの実装方式 — メモ化とタビュレーション

DPは実装方式により トップダウン・メモ化(Top-Down) と ボトムアップ・タビュレーション(Bottom-Up) に分かれる。メモ化は再帰呼び出しを保ちつつ計算結果をキャッシュ(配列・ハッシュマップ)へ保存し、同じ呼び出しが来れば即座に返す。コードが元の漸化式とほぼ同じで直観的であり、実際に必要な部分問題のみ計算する利点があるが、再帰呼び出しスタックの深さ制限と関数呼び出しオーバーヘッドが欠点である。

タビュレーションは最も小さな部分問題から表(table)を埋め上げ、大きな問題へ前進する。再帰がないためスタックオーバーフローがなく、反復文ベースで定数係数が小さいため概して速いが、すべての部分問題を漏れなく計算するため一部が不要でありうるし、計算順序を自ら設計せねばならない。以下の表は二方式の選択基準を整理したものであり、その違いは単なる好みではなく「不要な状態が多いか、再帰が深いか」という問題特性に由来する。

二方式の選択は実務で具体的な制約により分かれる。例えばnが10万を超えて再帰の深さが既定のスタック限界(Pythonの1,000、多くの言語で数万水準)を超える危険が大きければ、再帰ベースのメモ化はスタックオーバーフローで落ちうるため、タビュレーションが強制される。逆に状態空間が理論上は巨大であるが実際に訪れる状態はごく一部である「疎(sparse)」な問題では、必要な状態のみ計算するメモ化がメモリ・時間ともに有利である。すなわち選択の根拠はコードの好みではなく、状態空間の密度と再帰の深さという定量的特性である。

区分 メモ化(Top-Down) タビュレーション(Bottom-Up)
方向 大きな問題 → 小さな問題(再帰) 小さな問題 → 大きな問題(反復)
計算範囲 必要な部分問題のみ すべての部分問題
利点 直観的、疎な状態に有利 スタック安全、定数係数が小さい、空間最適化が容易
欠点 再帰オーバーヘッド・スタック限界 計算順序の設計が必要、不要計算の可能性
適した状況 状態空間が大きく疎 状態空間が密で全部必要

3. 動的計画法の設計手順

実務でDP問題を解く過程は、以下のような5段階の手順に定型化できる。この手順の核心はコーディングではなく、「状態(state)定義と漸化式の確立」というモデリング段階にある。

flowchart LR
  S1["1.状態定義<br/>(何を保存するか)"] --> S2["2.漸化式確立<br/>(状態間の関係)"]
  S2 --> S3["3.基底条件<br/>(初期値)"]
  S3 --> S4["4.計算順序<br/>(依存性の位相整列)"]
  S4 --> S5["5.解復元<br/>(逆追跡)"]

第1段階の状態定義 は「部分問題を一意に識別する変数」を定める作業である。例えばナップサック問題はdp[i][w]を「前のi個の物品のみ考慮し容量がwのときの最大価値」と定義する。状態を誤ると漸化式が成り立たないため、この段階が全体設計の成否を分ける。第2段階の漸化式 は状態間の依存関係を数式で表現する。第3段階の基底条件 は再帰が止まる最小状態の値を明示する(例:dp[0][*]=0)。第4段階の計算順序 はどの状態を先に埋めるべきかを依存性に従って位相整列することで、タビュレーションで特に重要である。第5段階の解復元 は最適値だけでなく「その値を作った選択(どの物品を詰めたか)」を逆追跡して復元する段階で、保存した決定経路を遡る。

この手順で初学者が最も頻繁に失敗する地点は第1~2段階である。状態を狭く取りすぎる(必要な情報を状態に収められない)と漸化式が過去の選択に依存して成り立たず、広く取りすぎると状態空間が爆発して複雑度が非現実的に大きくなる。したがって「現在の決定を下すのに必要な最小限の情報は何か」を問うことが状態定義の核心的な問いである。漸化式もまた「現在の状態をどのより小さな状態の組合せで表現できるか」という一文に還元され、このモデリングが書面で明確に整理されれば実装は機械的な作業に近い。技術士の答案でもコードではなく、まさにこの状態・漸化式・基底条件の三位一体を数式で提示することが評価の中心となる。

4. 代表事例

代表事例に入る前に、最も単純なフィボナッチでDPの効果を数値で確認しておくと、以後の事例が明瞭になる。fib(50)を単純再帰で解くと約2×10¹⁰回の関数呼び出しが発生し、普通のPCで数十秒かかるが、dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2]をボトムアップで埋めれば51回の加算で即座に終わる。さらにフィボナッチは直前の二値のみに依存するため、配列全体を持つ必要なく変数二つ(O(1)空間)だけでも計算される。この一例がDPの三つの核心 — 重複除去、空間・時間の交換、状態空間の最適化 — をすべて圧縮して示す。

A. 0/1ナップサック問題(0/1 Knapsack)

0/1ナップサック問題は、容量Wのナップサックに重さ・価値が与えられた物品を詰めて価値の合計を最大化するが、各物品は詰めるか詰めないか(0か1)の二者択一のみを選ぶ問題である。全探索は物品n個のすべての部分集合2ⁿを検査し指数的であるが、DPはdp[i][w] = max(dp[i-1][w], dp[i-1][w-重さᵢ] + 価値ᵢ)という漸化式でn×W個の状態のみ埋めてO(nW)で解く。例えばn=100, W=1000なら全探索は2¹⁰⁰(約10³⁰)回であるが、DPは10万回で終わり、実用性の境界を完全に越える。

注意すべき点は、このO(nW)が「擬多項式(pseudo-polynomial)」であることである。Wは入力の「値」であって「大きさ(ビット数)」ではないため、Wが非常に大きければ依然として非現実的である。0/1ナップサックがNP困難に分類されながらもDPで解ける理由がここにある。この事例は「DPの複雑度は状態空間の大きさに比例する」という原理と、その状態空間が入力値に依存するときの落とし穴を同時に示す。

B. 最長共通部分列(LCS)と編集距離

LCSは二つの文字列から順序を保ちつつ共通に取り出せる最も長い部分列を探す問題で、dp[i][j]を「文字列1の前のi文字と文字列2の前のj文字のLCS長」と定義する。文字が同じならdp[i-1][j-1]+1、異なればmax(dp[i-1][j], dp[i][j-1])で埋めてO(mn)で解く。編集距離(Levenshtein Distance)も挿入・削除・置換の三演算の最小回数を同じ2次元DPで求める。

この二つの事例は産業的に非常に広く使われる。LCSはgit diff・バージョン管理の差分比較、DNA配列整列(bioinformatics)の基盤であり、編集距離は綴り訂正・検索語の誤字補正・DNA類似度測定に使われる。例えば検索エンジンが「teh」という誤字を「the」へ訂正提案するとき、二つの単語の編集距離が小さいという事実をDPで計算して活用する。生成AIの出力評価指標の一つである文字列類似度も、この系列のDPに根ざしている。

C. フロイド・ワーシャル(全点対最短経路)

フロイド・ワーシャル(Floyd-Warshall)はグラフのすべての頂点対の間の最短経路を求めるDPアルゴリズムである。dp[k][i][j]を「頂点1~kのみ経由地として許すときのi→j最短距離」と定義し、経由地kを一つずつ増やしながらdp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])で更新する。三重のネストした反復でO(V³)にすべての対を求めるこのアルゴリズムは、ルーティングテーブル計算、ネットワーク遅延分析、交通網距離表の算出などに使われる。ダイクストラをすべての頂点で反復するより実装が簡潔で、負の重み(負の閉路を除く)も扱えるという利点がある。

フロイド・ワーシャルの教訓は「状態に経由地の次元を追加する」という発想である。最短経路を距離のみで定義すると漸化式が循環して成り立たないが、「経由可能な頂点集合」を段階変数kとして置けばkが単調増加する無閉路構造となり、DPが可能になる。このように状態をどう定義するかによって同じ問題が解けたり解けなかったりするという点が、DPで状態設計がなぜ核心であるかを端的に示す。

D. 最長増加部分列(LIS)

最長増加部分列(Longest Increasing Subsequence)は、数列から順序を保ちつつ取り出せる最も長い「増加する」部分列の長さを求める問題である。基本DPはdp[i]を「i番目の要素で終わるLIS長」と定義し、dp[i] = max(dp[j]) + 1(ただしj<iかつ要素ⱼ<要素ᵢ)で埋めてO(n²)で解く。例えば[10, 9, 2, 5, 3, 7, 101, 18]のLISは[2, 3, 7, 18]で長さ4であり、各位置で自分より小さい先行要素のdp値のうち最大を引き継ぐ方式で求める。

LISが教育的に重要である理由は、DPを他のデータ構造と結合してより速くする典型 であるからである。二分探索を接ぎ木すれば、各要素を「増加数列の末尾配列」へ挿入する位置をO(log n)で見つけ、全体をO(n log n)へ改善できる。これは「DPの漸化式自体はO(n²)であるが、遷移(transition)費用をデータ構造で減らして全体の複雑度を下げる」という上級の設計パターンで、セグメント木・フェニック木を結合したDP最適化の出発点となる。実務では作業スケジューリング、バージョン互換経路の探索、株価トレンド分析などに変形した形で使われる。

5. 分割統治・貪欲法との比較

三つのパラダイムはいずれも「問題を小さく分ける」という共通点があるが、部分問題の重複の有無と選択戦略で分かれる。以下の表はその違いを要約しつつ、違いが生じる「理由」まで併せて見る。

区分 動的計画法 分割統治 貪欲法
部分問題の重複 あり(保存・再利用) なし(独立) なし
展開方向 ボトムアップ/トップダウンとも トップダウン(再帰) 逐次的決定
選択方式 すべての場合を比較後に最適 分割後に併合 各段階で局所最適
最適性保証 常に(条件充足時) 分割基準に依存 貪欲選択性質が必要
代表例 ナップサック・LCS・フロイド 併合ソート・二分探索 釣銭・MST・ハフマン

分割統治とDPの決定的な違いは 部分問題の重複の有無 である。併合ソートは配列を半分に分けるが、二つの半分は完全に独立であるため再利用するものがない。一方フィボナッチはfib(n-1)とfib(n-2)がfib(n-2)を共有するため保存が利得になる。すなわち「分けた断片が互いに重なるか」がDPを使うか分割統治を使うかを分ける。

貪欲法とDPの違いは 選択の再考可能性 にある。貪欲法は各段階で最も良く見える選択をし、振り返らない。これが全体最適を保証するには「貪欲選択性質」が証明されねばならない。例えば分割可能な(fractional)ナップサックは単位重さあたり価値が高い順に詰める貪欲法が最適であるが、0/1ナップサックはそうではなく、必ずDPですべての場合を比較せねばならない。実務的含意は明白である — 貪欲法が正しければDPより速く簡単であるが、貪欲選択性質の証明に失敗すればDPへ安全に転換せねばならない。性急な貪欲適用は「大半は正しいがたまに誤る」最も危険なバグを生む。

実際、三つのパラダイムは排他的であるよりは連続線上にある。貪欲法は「各段階で一つの選択のみ残す特殊なDP」と見ることができ、分割統治は「部分問題が重ならない特殊なDP」と見ることができる。この観点から見れば、ある問題に出会ったとき、① 部分問題が重なるか(重ならなければ分割統治)、② 重なるなら各段階で一つの選択で十分か(十分なら貪欲、そうでなければ一般DP)を順に点検する意思決定の流れが自然に導かれる。技術士水準では個々のアルゴリズムの暗記を越えてこの判別の流れ自体を設計知識として体得し、与えられた業務問題にどのパラダイムが適するかを根拠とともに提示できねばならない。

6. 深化:状態空間の最適化と最新の活用

DPの実務的難題は状態空間がメモリを超過する場合である。代表的な解法が スライディングウィンドウ(rolling array)技法 で、漸化式が直前の行(dp[i-1])のみに依存すれば2次元配列を1次元へ圧縮し、空間をO(nW)からO(W)へ減らす。ナップサック問題で容量を逆順に巡回すれば1次元配列のみで正確に同じ答えを得るのがその例である。また状態をビットマスクへ符号化する ビットマスクDP(bitmask DP) は、外交員問題(TSP)など集合を状態とする問題をO(2ⁿ·n²)で解くが、これは全探索のO(n!)より画期的に速い。n=15なら15!(約1.3兆)と2¹⁵·15²(約740万)の違いで、DPの威力を改めて示す。

産業現場のもう一つの代表事例は金融工学のオプション価格決定である。アメリカ型オプション(満期前の早期行使が可能)の価値を求める二項木モデルは、満期時点の価値から逆に各時点・価格のノードの価値をmax(即時行使価値, 保有価値の割引期待値)で逆算するが、これは典型的なボトムアップDPである。またデータベースのクエリ最適化器(optimizer)は、複数テーブルの結合順序を定めるとき、部分集合別の最小費用結合計画をビットマスクDPで探索し、O(3ⁿ)で最適順序を見つける(System R以来の古典的技法)。通信分野のビタビ復号も畳み込み符号の最尤経路をDPで探すもので、DPがアルゴリズム教科書を越えて金融・DB・通信全般の中核エンジンであることを示す。

最新動向としては、DPが伝統的アルゴリズムを越えて機械学習・自然言語処理に深く浸透している点を挙げられる。音声認識・手書き認識の核心である隠れマルコフモデル(HMM)の復号はビタビ(Viterbi)アルゴリズムというDPで最適状態列を探し、DNA・タンパク質配列整列のNeedleman-Wunsch・Smith-Watermanアルゴリズムも編集距離系列のDPである。強化学習のベルマン方程式(Bellman Equation)は動的計画法の創始者の名をそのまま冠したもので、価値反復(Value Iteration)・方策反復(Policy Iteration)がいずれもDPの直接的応用である。技術士の観点からDPは単なるコーディング技法ではなく、最適意思決定を多段階に分解する汎用の思考枠組みとして理解すべきである。

想定出題方向としては、① 特定問題(ナップサック・LCS・最長増加部分列など)の漸化式・複雑度の導出、② 分割統治・貪欲法との比較および適用条件の判別、③ メモ化/タビュレーションの選択根拠、④ 擬多項式複雑度とNP困難の関係などが有力である。答案作成時には漸化式を必ず明示し、状態空間の大きさで複雑度を導出し、「なぜ貪欲/分割統治ではなくDPか」の根拠(最適部分構造・重複部分問題)を併せて述べることが高得点戦略である。

具体的な答案構成戦略を例示すると、1時限目の短答型でも「定義 → 成立条件二つ → 代表漸化式一つ(例:ナップサック) → 複雑度 → 他技法との一行比較」の骨格を備えれば深さが表れる。2・3時限目の論述型であればここに ⓐ 概念図(全探索対DPの違い)、ⓑ 設計5段階の手順、ⓒ 二つ以上の事例別の漸化式と複雑度の導出、ⓓ 状態空間の最適化(スライディングウィンドウ・ビットマスキング)技法、ⓔ 技術士観点の適用判断(擬多項式の落とし穴、パラダイム選択の流れ)を層層に積む。特に採点者は「漸化式を立てられるか」と「適用条件を判別できるか」を核心の弁別点と見るため、暗記した結果ではなく状態定義から漸化式に至る思考過程を叙述で表すことが決定的である。

7. 考慮事項および示唆点

  1. 適用条件の事前検証(正確性):DPは万能ではない。最適部分構造と重複部分問題がともに成り立つかをまず検証せねばならず、最長単純経路のように部分解の結合が全体解を保証しない問題にDPを適用すると誤った答えを出す。設計前に「部分解を結合して全体解になるか」を必ず証明する。
  2. 空間・時間トレードオフの管理(資源効率):DPは時間をメモリと交換する。状態空間がメモリ限界を超えれば、スライディングウィンドウ・状態圧縮・疎な保存(ハッシュマップ)などで空間を減らす設計が必須である。組込み・大容量環境ではこの最適化の有無が適用可能性を左右する。
  3. 擬多項式複雑度の落とし穴(性能判断):ナップサック問題のO(nW)のように複雑度が入力の「値」に比例すれば、値が大きいとき事実上指数的に遅くなる。NP困難問題がDPで解けるからといってすべての規模で実用的なわけではないため、入力範囲を根拠に適用の妥当性を判断する。
  4. パラダイム選択の戦略(設計判断):貪欲法が成り立てばDPより速く簡単であるため先に検討するが、貪欲選択性質の証明に失敗すればDPへ転換する。部分問題が独立なら分割統治が正しい。三つのパラダイムを排他的に見ず、問題特性に従って選択・結合する眼力が技術士の力量である。
  5. 汎用思考枠組みへの拡張(展望・連携技術):DPは強化学習(ベルマン方程式)、配列整列(バイオインフォマティクス)、音声・手書き認識(ビタビ)などへ拡張される汎用の最適化枠組みである。伝統的アルゴリズムを越えてAI・データ分野の基盤技術として連携して理解すれば応用範囲が大きく広がる。

参考資料

  • Cormen et al., "Introduction to Algorithms", MIT Press(動的計画法・最適部分構造)
  • R. Bellman, "Dynamic Programming", Princeton University Press, 1957
  • cp-algorithms, Dynamic Programming: https://cp-algorithms.com/dynamic_programming/

一言まとめ: 動的計画法は、最適部分構造と重複部分問題 が成り立つ問題を部分問題へ分解しその解を保存・再利用することで指数的探索を多項式時間へ減らす技法であり、メモ化/タビュレーションで実装し、貪欲・分割統治と異なり「すべての場合を比較するが重複は一度だけ計算する」という設計判断が核心である。