動的プログラミング（DP）とは何ですか？

問題を小さな部分問題に分割し、解を記録して再利用するアルゴリズム設計手法。重複計算を排除して効率化する。

動的プログラミング（DP）のポイントは？

最適部分構造（大きな問題の最適解が小さな問題の最適解から構成される）。重複部分問題（同じ部分問題が何度も現れる）。メモ化（トップダウン）とテーブル法（ボトムアップ）の2つのアプローチ。ナップサック問題、最長共通部分列、フィボナッチ数列が典型例

【どうてきぷろぐらみんぐ】

動的プログラミング（DP）とは？

💡 「小さい問題の答えを積み上げて」大きな問題を解く

📌 このページのポイント

最適部分構造（大きな問題の最適解が小さな問題の最適解から構成される）
重複部分問題（同じ部分問題が何度も現れる）
メモ化（トップダウン）とテーブル法（ボトムアップ）の2つのアプローチ
ナップサック問題、最長共通部分列、フィボナッチ数列が典型例

動的計画法（メモ化）のイメージ

ひよこ

具体的にどういうこと？

ペンギン先生

フィボナッチ数列fib(5)を普通に再帰で計算すると、fib(3)が2回、fib(2)が3回計算される。DPでは一度計算した結果をテーブルに保存して再利用する。fib(1)=1, fib(2)=1を出発点にfib(3)=2, fib(4)=3, fib(5)=5と順番に計算すれば無駄がない。指数時間O(2^n)が線形時間O(n)になるんだよ

ひよこ

メモ化とテーブル法の違いは？

ペンギン先生

メモ化（トップダウン）は再帰で大きな問題から始めて、必要な部分問題だけを計算して記録する。テーブル法（ボトムアップ）は小さな問題から順に解いてテーブルを埋めていく。結果は同じだけど、テーブル法の方がスタックオーバーフローのリスクがなく、メモリ効率を最適化しやすいよ

ひよこ

競技プログラミングで頻出って本当？

ペンギン先生

超頻出だよ。AtCoderのABC-D〜E問題でDPはほぼ毎回出る。ナップサック問題、区間DP、桁DP、木DP、ビットマスクDP…種類が多くて難しいけど、パターンを覚えれば解ける問題が増える。「この問題はDPで解ける」と気づけるかが最初のハードルだね

ひよこ

実務でDPを使う場面は？

ペンギン先生

①テキストの差分検出（diff、git diff）→最長共通部分列のDP、②自然言語処理（動的時間伸縮法）、③ルート最適化（最短経路問題）、④リソース割り当て最適化。日常的に使うツールの裏側でDPが活躍していることは多いよ

まとめ：ざっくりこれだけ覚えればOK！

「動的プログラミング」って出てきたら「部分問題の解を再利用して効率的に解くアルゴリズム手法」と思えればだいたいOK！

📖 おまけ：英語の意味

「Dynamic Programming」＝動的計画法

💬 Richard Bellmanが1950年代に命名。「Dynamic」は数学的に響きが良いから選んだだけで深い意味はないよ

← 用語集にもどる

動的プログラミング（DP） とは？

動的プログラミング（DP）とは？