Java | 「動的計画法」を体系的に理解する

Java

2026.07.17

Javaで学ぶ「動的計画法」を体系的に理解する（前半）
動的計画法とは何か（やさしい定義）
再帰と動的計画法の関係
フィボナッチ数列で見る「再帰」と「DP」の違い
フィボナッチを動的計画法で書く（一次元DP）
深掘り：このコードのどこが「動的計画法」なのか
一次元DPの基本パターンを体に染み込ませる
再帰との違いをもう一度整理する
前半のまとめと後半への橋渡し

Javaで学ぶ「動的計画法」を体系的に理解する（前半）

動的計画法（Dynamic Programming, DP）は、アルゴリズムの世界で非常に重要なテクニックです。「難しそう」「数学っぽくて怖い」と感じる読者も多いですが、本質はとてもシンプルで、一言でいえば「同じ計算を二度しないように、うまく結果を使い回す方法」です。

前半では、Javaを使いながら

動的計画法とは何か
再帰との関係
フィボナッチ数列を題材にした基本パターン
一次元DPの考え方

を、初心者向けにかみ砕いて解説していきます。後半では、二次元DP（表を使うDP）や、典型問題（ナップサック、最長共通部分列など）に踏み込みます。

動的計画法とは何か（やさしい定義）

動的計画法を一言で説明すると、

「問題を小さな部分問題に分けて、その結果を表や配列に保存しながら、小さいものから順番に解いていく方法」

です。

ここで重要なのは次の二つのポイントです。

再利用できる「部分問題」があること一度解いた部分問題の結果を、別の計算で何度も使うことができる。

その結果を保存しておくこと配列やテーブルに結果を記録し、後から参照することで、同じ計算を二度しない。

この二つがそろったとき、動的計画法が威力を発揮します。

再帰と動的計画法の関係

前のテーマで扱ったように、再帰は「大きな問題を小さな問題に分割して、自分自身に任せる」スタイルでした。動的計画法は、その再帰の考え方を「より効率的に」「より体系的に」したものだと捉えると分かりやすいです。

再帰は「上から下へ」大きな問題を分割していくイメージ。動的計画法は「下から上へ」小さな問題から順番に積み上げていくイメージ。

どちらも「部分問題を使って全体を解く」点では同じですが、動的計画法は「重複計算をしない」「配列や表を使う」という点で、より実務向きです。

フィボナッチ数列で見る「再帰」と「DP」の違い

動的計画法の入門として、定番のフィボナッチ数列を題材にします。

フィボナッチ数列は次のように定義されます。

F(0) = 0 F(1) = 1 F(n) = F(n – 1) + F(n – 2)

まずは、素朴な再帰で書いてみます。

public static int fibRecursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

public static int fibRecursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Java

このコードは「定義そのもの」を表現していて、とても美しいです。しかし、fibRecursive(40) などを計算すると、非常に時間がかかります。

理由は、同じ値を何度も何度も計算しているからです。例えば fibRecursive(5) の中で fibRecursive(3) や fibRecursive(2) が何度も登場します。

フィボナッチを動的計画法で書く（一次元DP）

動的計画法を使うと、この重複計算を完全に消すことができます。

フィボナッチを一次元配列で解くコードは次のようになります。

public static int fibDP(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

public static int fibDP(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

Java

ここで dp[i] は「F(i) の値」を表しています。小さい i から順番に dp[2], dp[3], ... dp[n] を計算していき、最後に dp[n] を返します。

深掘り：このコードのどこが「動的計画法」なのか

フィボナッチの DP コードを、動的計画法の観点から分解してみます。

部分問題の定義「F(i) を求める」という小さな問題を、dp[i] という形で表現している。

漸化式（状態遷移）の定義 dp[i] = dp[i - 1] + dp[i - 2] これは「F(i) は F(i-1) と F(i-2) から計算できる」という関係をコードにしたもの。

初期条件（ベースケース）の設定 dp[0] = 0 dp[1] = 1 ここからスタートして、順番に値を埋めていく。

この三つがそろったとき、「動的計画法」と呼べる形になります。

部分問題漸化式（状態遷移）初期条件

この三つは、動的計画法を体系的に学ぶうえで非常に重要なキーワードです。

一次元DPの基本パターンを体に染み込ませる

フィボナッチは一次元DPの最も基本的な例です。一次元DPとは、「一つの整数 i に対して dp[i] を定義する」タイプの動的計画法です。

他にも、次のような問題が一次元DPの典型です。

階段の登り方の数（1段 or 2段ずつ登る場合の通り数）最小コストである地点まで進む問題連続部分列の最大和（Kadane のアルゴリズムに近いもの）

例えば「階段の登り方」を考えてみましょう。 1段または2段ずつ登れるとき、n段の階段を登る方法の数を求める問題です。

この問題も、フィボナッチとほぼ同じ構造を持っています。

dp[i] = dp[i – 1] + dp[i – 2]

「最後に1段登った場合」と「最後に2段登った場合」の合計が dp[i] になるからです。

コードは次のように書けます。

public static int waysToClimb(int n) {
    if (n == 0) return 1; // 何もしない1通り
    if (n == 1) return 1;

    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

public static int waysToClimb(int n) {
    if (n == 0) return 1; // 何もしない1通り
    if (n == 1) return 1;

    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

Java

このように、「dp[i] をどう定義するか」「dp[i] を dp[i-1], dp[i-2] からどう計算するか」を考えるのが、一次元DPの基本パターンです。

再帰との違いをもう一度整理する

同じ階段の問題を再帰で書くこともできます。

public static int waysRecursive(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    return waysRecursive(n - 1) + waysRecursive(n - 2);
}

public static int waysRecursive(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    return waysRecursive(n - 1) + waysRecursive(n - 2);
}