プログラミングの勉強を進めていくと、「動的計画法（DP）」という言葉をよく耳にするようになります。競技プログラミングやアルゴリズムの問題では定番の手法ですが、「聞いたことはあるけど、いまいち仕組みや使い方が分からない……」という方も多いのではないでしょうか。この記事では、動的計画法の基本的な考え方から、よくあるパターン、実際の問題への応用方法まで、初心者にも分かりやすく丁寧に解説します。ぜひ、DPのコツをつかんで、アルゴリズム問題のレベルアップを目指しましょう！
動的計画法（DP）とは何か？
動的計画法（Dynamic Programming、略してDP）は、「ある大きな問題を、小さな部分問題に分割して、それらを解いていくことで、最終的な答えを効率的に求める」アルゴリズムの手法です。
一度解いた部分問題の答えを保存（メモ化）しておき、同じ問題を繰り返し解かずに済むことで、無駄な計算を省くことができます。
例えば、フィボナッチ数列を再帰的に求めると、同じ計算を何度も繰り返してしまい、計算量が爆発的に増えます。
そこで、既に計算した結果を保存しておけば、必要なときにすぐに利用できる――これが動的計画法の根本的な考え方です。
DPのポイント：「部分問題」「メモ化」「再利用」
動的計画法を使いこなすには、次の3つのポイントを押さえることが重要です。
- 部分問題に分解する
最初に解きたい大きな問題を、小さく分けて考えます。 - 部分問題の結果を保存（メモ化）する
同じ部分問題を何度も計算しないように、計算結果を配列や辞書などに保存します。 - 保存した結果を再利用する
必要なときに保存した結果を取り出して使い、全体の効率を上げます。
フィボナッチ数列でDPを体感してみよう
まずは有名な例である「フィボナッチ数列」を使って、動的計画法の考え方を実際に見てみましょう。
フィボナッチ数列の問題
フィボナッチ数列は次のように定義されます。
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （n ≥ 2）
これを再帰関数で書くと、とてもシンプルですが、計算量が多くなってしまいます。
再帰のみの場合
def fib(n):
if n == 0 or n == 1:
return n
return fib(n-1) + fib(n-2)
この実装だと、例えばfib(5)を求めるとき、fib(3)やfib(2)など同じ計算を何度も行っています。
DP（メモ化再帰、トップダウン）で解決！
memo = {}
def fib(n):
if n == 0 or n == 1:
return n
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
このように、計算した値をmemoという辞書に保存し、必要なときにすぐ取り出します。
DP（配列を使ったボトムアップ）
def fib(n):
dp = [0] * (n+1)
if n == 0:
return 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
このように、「小さい問題から順に計算していく」のがボトムアップ型のDPです。
DPの種類：トップダウン（メモ化再帰）とボトムアップ（配列表）
動的計画法には、大きく分けて「トップダウン」と「ボトムアップ」の2種類の実装方法があります。
| 手法 | 特徴 | メリット | デメリット |
|---|---|---|---|
| トップダウン | 再帰 + メモ化で、必要なものだけ計算 | 実装が直感的で書きやすい | スタックオーバーフローに注意 |
| ボトムアップ | 配列を使い、小さい順からすべて計算 | メモリ使用量が分かりやすい | 全て計算する必要がある場合もある |
DPが活躍する代表的な問題パターン
動的計画法が役立つのは、「部分問題の答えを使い回せる」ような問題です。よくあるパターンは以下の通りです。
1. ナップサック問題（部分和問題）
重さと価値が決まった複数の品物から、制限された重さの中で最大の価値を得るには、どの品物を選べばよいか？
このような「選び方の組み合わせを効率よく探索したい」ときにDPが使われます。
2. 最長増加部分列（LIS）
数列から、昇順に並んだ部分列で、最も長いものの長さを求めよ。
部分問題として「ある位置までのLISの長さ」を保存して再利用します。
3. 最小コスト経路問題
2次元グリッドで、左上から右下まで移動する際、通過するマスの合計コストが最小になる経路を求めよ。
この場合も、各マスまでの最小コストをDP配列に保存していきます。
DPでよく使う配列表設計
動的計画法を使いこなすためには、「どんなDP配列を用意するか」を考えるのが重要です。
次のような例を紹介します。
1次元DP配列
- 例：フィボナッチ数列、LISなど
- 配列
dp[i]に「i番目までの最適解」を保存
2次元DP配列
- 例：ナップサック問題、グリッド移動
- 配列
dp[i][j]に「i個目までの品物、重さjまでで得られる価値」や「座標(i, j)までの最小コスト」を保存
3次元DP配列
- 複数の状態を管理したいときに使います
- 例：スケジューリング問題や状態遷移を管理する問題
DP配列表の設計例：ナップサック問題
ナップサック問題のDP配列表の設計例を見てみましょう。
問題設定
- 品物の個数：N個
- 各品物の重さ：w[i]
- 各品物の価値：v[i]
- ナップサックの容量：W
DP配列
dp[i][j]= 「i個目までの品物で、重さj以下で得られる最大の価値」
遷移式
- 品物iを選ばない場合：
dp[i+1][j] = dp[i][j] - 品物iを選ぶ場合（重さ制限内）：
dp[i+1][j + w[i]] = max(dp[i+1][j + w[i]], dp[i][j] + v[i])
実装例
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
wi, vi = map(int, input().split())
w.append(wi)
v.append(vi)
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
for j in range(W+1):
# 品物iを選ばない場合
dp[i+1][j] = max(dp[i+1][j], dp[i][j])
# 品物iを選ぶ場合
if j + w[i] <= W:
dp[i+1][j + w[i]] = max(dp[i+1][j + w[i]], dp[i][j] + v[i])
# 答えは dp[N][W] ではなく、dp[N][j] (j=0～W) の最大値
ans = max(dp[N])
print(ans)
DP設計のための4つのステップ
動的計画法の問題を解くときは、次の4ステップで考えると分かりやすいです。
- 状態（DP配列）を定義する
どんな情報を持った配列・辞書にするか決める。 - 初期値を決める
最初にどんな値が入っているべきか決める。 - 遷移（状態の更新）を考える
どうやって次の状態を計算するか式を考える。 - 答えを取り出す
DP配列のどこが最終的な答えになるか確認する。
DPの実践的なコツ
- 配列の次元数に注意する
必要以上に多次元にするとメモリ消費が大きくなります。できるだけ1次元や2次元で工夫しましょう。 - 状態の圧縮や遷移の工夫
問題によっては、「今と1つ前だけ持てばいい」など省メモリ化できることもあります。 - サンプルケースでテストする
小さい入力例で手計算してみると、DP配列や遷移式が正しいか確かめやすいです。
DPによくあるエラーと解決法
| エラー例 | 解決法 |
|---|---|
| 配列の初期化ミス | 0や-1、float("inf")など、適切な初期値を確認する |
| インデックスの範囲外アクセス | for文の範囲やif条件を確認し、配列のサイズと一致しているかチェックする |
| 遷移式のミス | 手計算やデバッグプリントでどこが間違っているか確かめる |
DPは「部分問題を保存して賢く使い回す」魔法のテクニック！
動的計画法（DP）は、アルゴリズムの世界でとても強力なテクニックです。
「今まで再帰や全探索で時間がかかっていた問題」が、DPを使うことで一気に高速化できる場合もたくさんあります。
コツをつかむまでは少し難しく感じるかもしれませんが、いくつかのパターンを覚えて、実際に手を動かしながら問題を解いていくことで、自然と身についてきます。
分からないところはこの記事を見返しながら、ぜひ色んなDP問題に挑戦してみてください！
コメント