動的計画法（DP）とは｜競技プログラミング初心者向けにわかりやすく解説

動的計画法（DP）とは

動的計画法（Dynamic Programming、略して DP）は、大きな問題を小さな部分問題に分けて、答えを表に記録しながら順番に計算していくアルゴリズムです。

DP のエッセンスは、たった 2 つです。

1. 小さな問題の答えを使って、大きな問題の答えを作る
2. 一度計算した答えは表に記録して、二度と計算し直さない

「全部の組み合わせを試す全探索だと間に合わないけど、よく見ると同じ計算を何度もしている」——そんなときに、結果をメモしながら効率よく計算するのが DP です。

JOI でも頻出のテーマで、二次予選から本選にかけて多くの問題で使われます。「最初は何をやっているのかさっぱり分からない」と感じる人が多いアルゴリズムですが、遷移の作り方のコツさえ掴めれば、一気に解ける問題の幅が広がります。

まずはイメージから：階段の上り方

DP の考え方は、次のような問題を考えるとわかりやすいです。

N 段の階段がある。一度に 1 段 か 2 段 上ることができる。1 段目から N 段目まで上る方法は何通りあるか？

例えば N = 4 の場合、答えは 5 通りです（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）。

これを N = 30 とか N = 100 にしたとき、全パターンを書き出すのは大変です。でも、ちょっと視点を変えてみると、驚くほどシンプルに解けます。

「N 段目に来る方法」を考える

N 段目に到達する直前の状態は、必ず次のどちらかです。

• (N-1) 段目 から 1 段上って来た
• (N-2) 段目 から 2 段上って来た

ということは、

(N 段目までの上り方の数)
　= (N-1 段目までの上り方の数) + (N-2 段目までの上り方の数)

という関係が成り立ちます。

この「前の答えを使って今の答えを作る」という関係式を、漸化式（ぜんかしき）と呼びます。DP の核となる考え方です。

表に書き出してみる

dp[i] = i 段目までの上り方の数 として、小さい i から順に表を埋めていきましょう。

i	0	1	2	3	4	5	6
dp[i]	1	1	2	3	5	8	13

• dp[0] = 1（出発地点。何もしない 1 通り）
• dp[1] = 1
• dp[2] = dp[1] + dp[0] = 2
• dp[3] = dp[2] + dp[1] = 3
• dp[4] = dp[3] + dp[2] = 5
• ...

このように、小さい方から順番に表を埋めていくだけで、N がどんなに大きくても答えが計算できます。これが DP の基本的な進め方です。

DP の 3 ステップ

DP は、どんな問題でも次の 3 ステップで考えると整理しやすいです。

1. 状態を決める：「dp[i] が何を表すか」を言葉で定義する
2. 遷移を作る：「dp[i] は、もっと小さい dp[?] からどう作れるか」を考える
3. 初期値と答えを決める：dp[0] などの最初の値、最終的に欲しい答えがどこに入るか

階段問題の場合、

1. 状態：dp[i] = i 段目までの上り方の数
2. 遷移：dp[i] = dp[i-1] + dp[i-2]
3. 初期値：dp[0] = 1, dp[1] = 1、答えは dp[N]

という形になります。この 3 ステップを言葉で書けるようになるのが、DP マスターへの第一歩です。

C++ での実装

階段問題を C++ で書くとこうなります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<long long> dp(N + 1, 0);
    dp[0] = 1; // 初期値
    dp[1] = 1;

    // 小さい i から順に埋めていく
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[N] << endl;
    return 0;
}

ループ 1 周で表が完成するので、計算量は O(N) です。N = 100 万でも一瞬で答えが出ます。全探索（全パターンを書き出す）だと答えの個数自体が指数的に増えるので、それと比べると圧倒的に高速です。

2 次元 DP：ナップサック問題

実際の問題、とくに二次予選のような難しい問題では、2 次元の DP（状態を 2 つ以上持つ DP）が頻出です。その代表例がナップサック問題です。

N 個の品物があり、品物 i は重さ w[i]、価値 v[i] を持つ。重さの合計が W 以下になるように品物を選ぶとき、価値の合計の最大値を求めよ。

「選ぶか選ばないか」を 1 個ずつ決める全探索だと 2ᴺ 通りに膨らみ、N = 30 を超えると間に合いません。ところが DP を使えば O(N × W) という現実的な計算量で解けます。状態の置き方や遷移の作り方を学ぶのに最適な題材で、JOI 二次予選以降でも頻出です。

考え方の詳細・実装・関連する典型問題（経路数、最長共通部分列など）を体系的に学びたい方は、ぜひ HaruCoder の無料体験 を覗いてみてください。難易度順の問題と自動採点で、DP の応用を段階的にマスターできます。

計算量：DP が速い理由

DP が速いのは、同じ部分問題を二度と計算し直さないからです。

例えば階段問題で、もし「N 段目までの上り方を、毎回 1 から数え直す」と、同じ dp[3] の値が何度も計算されることになります。N が大きくなると、計算の重複は指数関数的に増えていきます。

DP は、**「一度解いた問題は表に記録して使い回す」**ことで、この無駄をすべて削ります。これが「指数時間 → 多項式時間」というジャンプの正体です。

問題	全探索	DP
階段問題	O(2ᴺ) 相当	O(N)
ナップサック問題	O(2ᴺ)	O(N × W)
経路数を数える	O(指数)	O(H × W)

メモ化再帰という書き方

DP には大きく分けて 2 つの書き方があります。

• 配るDP / もらうDP（forループ）：小さい方から表を埋める。今回紹介してきた書き方
• メモ化再帰（関数）：再帰関数で書き、計算結果を表に保存して使い回す

メモ化再帰は「漸化式をそのまま再帰関数として書く」イメージです。例えば階段問題なら、

vector<long long> memo;

long long solve(int n) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n]; // 計算済みならそれを返す
    return memo[n] = solve(n - 1) + solve(n - 2); // 計算して記録
}

というふうに書けます。漸化式から自然に書きやすいのがメリットですが、再帰の深さに気をつける必要があります。最初はボトムアップ、慣れたらメモ化再帰、という順で身につけるのがオススメです。

つまずきやすいポイント

1. 状態を言葉で定義できていない

DP がうまくいかないときの 9 割は、状態の定義が曖昧であることが原因です。「dp[i][j] って何？」と聞かれて、完全な日本語の文章で答えられるかどうかをチェックしましょう。

✅ dp[i][j] = 品物 0〜(i-1) から選び、重さ j 以下のときの価値の最大値
❌ dp[i][j] = なんとなく i と j に関する DP の値

定義がしっかりすれば、遷移は自然と出てきます。

2. 初期値の設定ミス

dp[0] などの初期値は、問題の意味と整合するように設定しなければなりません。

• 「方法の数を数える」問題 → dp[0] = 1（何もしない 1 通り）
• 「最大値を求める」問題 → dp[0] = 0、未定義のところは -INF で埋める
• 「最小値を求める」問題 → 未定義のところは INF で埋める

特に、「ありえない状態」と「答えが 0 の状態」を区別するのが大事です。0 で初期化していたら、「ありえない経路」も「コスト 0 の経路」と見分けがつかなくなります。

3. 配列の添字ずれ

dp[i][j] の i が「i 個目の品物まで使った」を意味するのか、「i 番目の品物（インデックス i）を最後に使った」を意味するのかで、配列の参照位置がズレます。

迷ったら、**「dp[i][j] は何を表す？」**を最初に紙に書いて、それに沿って実装しましょう。

4. オーバーフロー

DP の値は意外と大きくなりがちです。経路数のような問題は、N = 60 あたりで int の範囲を超えます。基本は long long で持っておくのが安全です。

まとめ

DP のポイントをもう一度整理しておきましょう。

• 小さい問題の答えを表に記録して、それを使って大きな問題を解くアルゴリズム
• 状態の定義 → 遷移 → 初期値の 3 ステップで考える
• 同じ部分問題を何度も解かないので、指数時間 → 多項式時間へと劇的に速くなる
• ナップサック問題、経路数、最長共通部分列など、応用は無限大

DP は最初は「何をやっているか分からない」となりがちですが、典型問題を 5〜10 個自分の手で書くと、急に視界が開けます。JOI 二次予選以降の主力武器なので、ぜひマスターしてください。

練習問題に挑戦しよう

アルゴリズムは「読んで理解した」だけでは使えるようになりません。実際に自分の手で書いて、問題を解くことで初めて身につきます。

HaruCoder のオンライン受講では、DP を使う問題を難易度順に用意しており、提出すれば自動で採点されます。「次に何を解けばいいかわからない」という悩みもなく、段階的にステップアップできます。

また、まだ競技プログラミングを始めたばかりで「そもそもどうやって問題を解くの？」という方は、先に以下の記事を読んでみてください。

• 競技プログラミングの始め方 — ブラウザだけで 1 問解く流れを画像付きで解説
• JOIの難易度全解説 — DP が実際に役立つコンテストの全体像