Java | Tree Dynamic Programming

Java Java
スポンサーリンク

Javaで学ぶ「木DP（Tree Dynamic Programming）」（前半）

木DP（Tree DP）は、動的計画法（Dynamic Programming）と木構造（ツリー）が組み合わさったテクニックです。 競技プログラミングやアルゴリズムの世界ではよく登場しますが、 「名前が難しそう」で敬遠されがちなテーマでもあります。

前半では、まず 「そもそも動的計画法とは何か」 「木構造とは何か」 「なぜ木とDPを組み合わせると強力なのか」 を、できるだけ直感的にかみ砕いて説明します。 そのうえで、シンプルな木DPの例を Java コードで追いながら、 「木DPの基本パターン」をつかむことを目標にします。

動的計画法（DP）を「部分問題を使い回す」という視点で理解する

木DPに入る前に、まず「DPとは何か」を整理しておきます。 動的計画法は、一言で言うと「同じ計算を何度もやらないようにするテクニック」です。

例えば、フィボナッチ数列を素直な再帰で書くと、 同じ値を何度も計算してしまい、ものすごく遅くなります。

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

このコードでは、fibRecursive(5) を計算するために fibRecursive(4) と fibRecursive(3) を呼び、 さらにその中で fibRecursive(3) や fibRecursive(2) が何度も呼ばれます。

動的計画法では、「一度計算した結果を覚えておいて、次回はそれを使う」ことで この無駄をなくします。

public static int fibDP(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    if (n >= 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] に「F(i) の値」を保存しながら進んでいます。 この「部分問題の答えを配列やテーブルに保存して使い回す」という考え方が、DPの核心です。

木DPは、この「部分問題を使い回す」という考え方を、木構造に持ち込んだものです。

木構造（ツリー）を「親と子の階層」としてイメージする

次に、木構造を整理します。 木は「親と子の関係を持つ階層構造」です。

Javaで最もシンプルな木の表現は、次のようなクラスです。

import java.util.ArrayList;
import java.util.List;

class Node {
    int value;
    List<Node> children = new ArrayList<>();

    Node(int value) {
        this.value = value;
    }

    void addChild(Node child) {
        children.add(child);
    }
}
Java

例えば、次のような木を作ることができます。

Node root = new Node(5);
Node child1 = new Node(3);
Node child2 = new Node(7);
root.addChild(child1);
root.addChild(child2);

Node grandChild = new Node(2);
child1.addChild(grandChild);
Java

この木は、 根（root）が 5 その子が 3 と 7 3 の子が 2 という階層構造になっています。

木構造の重要なポイントは、「親も子も同じ Node 型」であり、 どの部分を切り取っても「それ自体が木になっている」ということです。 この「部分も全体も同じ形」という性質が、DPと非常に相性が良いのです。

木DPとは何か：「部分木ごとに答えを持つ」という発想

木DPの本質は、「各ノードを根とする部分木に対して、何らかの値を計算しておく」という発想です。

例えば、次のような問題を考えてみます。

「各ノードに整数 value が入っている木がある。 そのノードを根とする部分木の合計値を求めたい。」

つまり、 あるノードを見たときに「そのノード以下の全部の value の合計」を知りたい、 という問題です。

このとき、木DPでは「各ノードに対して、その部分木の合計値を dp として持つ」 という形で考えます。

例題：部分木の合計値を木DPで求める

先ほどの Node クラスを使って、 「各ノードを根とする部分木の合計値」を求める木DPを書いてみます。

public class TreeDPExample {

    public static int computeSubtreeSum(Node node) {
        int sum = node.value;

        for (Node child : node.children) {
            sum += computeSubtreeSum(child);
        }

        node.value = sum; // ここでは、value を「部分木の合計」に更新してしまう例
        return sum;
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        Node child1 = new Node(3);
        Node child2 = new Node(7);
        root.addChild(child1);
        root.addChild(child2);

        Node grandChild = new Node(2);
        child1.addChild(grandChild);

        computeSubtreeSum(root);

        System.out.println("root subtree sum: " + root.value);       // 5 + 3 + 2 + 7 = 17
        System.out.println("child1 subtree sum: " + child1.value);   // 3 + 2 = 5
        System.out.println("child2 subtree sum: " + child2.value);   // 7
        System.out.println("grandChild subtree sum: " + grandChild.value); // 2
    }
}
Java

このコードの動きを丁寧に追ってみます。

computeSubtreeSum(node) は、 「node 自身の value と、子の部分木の合計値を足し合わせる」メソッドです。

まず、sum に node.value を入れます。 次に、すべての子 child に対して computeSubtreeSum(child) を呼び、 その結果を sum に足していきます。

最後に、その sum を返しつつ、 ここでは例として node.value を「部分木の合計値」に更新しています。

重要なのは、 「子の部分木の合計値を先に計算して、それを親の計算に使っている」 という点です。

これがまさに「木DP」です。 各ノードを根とする部分木の答えを、 再帰的に計算しながら上に伝えていく構造になっています。

深掘り：なぜこれは「DP」なのか

この例を「DP」として見ると、次のような構造になっています。

部分問題は「あるノードを根とする部分木の合計値」です。 その答えは「子の部分木の合計値」を使って計算されています。

つまり、 「子の部分問題の答えを使って、親の部分問題の答えを計算している」 という形になっています。

フィボナッチの DP では、 dp[i] = dp[i - 1] + dp[i - 2] という形で「小さい i の答えを使って大きい i の答えを計算」しました。

木DPでは、 「子ノードの答えを使って親ノードの答えを計算」します。

この「部分問題の答えを使い回す」という構造が、 DPの本質であり、木DPにもそのまま現れています。

木DPの基本パターンを言語化する

木DPの基本パターンは、次のように言語化できます。

「各ノードに対して、そのノードを根とする部分木に関する値を定義する。 その値を、子ノードの値を使って再帰的に計算する。」

この「値」が何かは問題によって変わります。

部分木の合計値 部分木の最大値・最小値 部分木の高さ（深さ） 部分木の中で条件を満たすノード数 など、さまざまなバリエーションがあります。

重要なのは、 「子の答えを使って親の答えを計算できるように、値の定義を工夫する」 という発想です。

この発想が身につくと、 木DPの問題を見たときに 「どんな値を持たせれば、子から親へうまく計算を伝えられるか」 を考えられるようになります。

前半のまとめと後半への橋渡し

前半では、木DPを理解するための土台として

動的計画法（DP）とは「部分問題の答えを使い回す」テクニックであること 木構造（ツリー）が「親も子も同じ形をしている」階層構造であること 木DPとは「各ノードを根とする部分木に対して値を定義し、子の値を使って親の値を計算する」こと 具体例として「部分木の合計値」を求める木DPを Java で実装し、その動きを追うこと

を丁寧に整理しました。

後半では、さらに一歩進んで

部分木の高さ・最大値・条件付きカウントなど、別の木DPの例 「根から見たDP」と「子から見たDP」の違い（根付き木と再根付き） 計算量・スタックの深さ・セキュリティの観点から見た木DPの注意点 競技プログラミングや実務で木DPが登場する具体的な場面

を、より踏み込んで解説していきます。

次へ
12
スポンサーリンク
タイトルとURLをコピーしました