每日算法 — 使用java实现树形DP：树上动态规划与最大独立集问题

引言

动态规划是解决多阶段决策问题的利器，而当决策结构本身是一棵树时，传统的线性DP便需要升级为树形DP。树形DP充分利用树的层次结构和子问题的独立性，通过自底向上的递归合并子树结果，高效求解诸如树的最大独立集、最小点覆盖、树的直径、树链剖分等一系列经典问题。本文以”树的最大独立集”为核心场景，用Java完整实现树形DP框架，并拓展到树的最小顶点覆盖和最大权独立集问题。

问题定义

树的最大独立集（Maximum Independent Set on Tree）：给定一棵树，每个节点有一个权重（或权重为1），要求选出一个节点子集，使得子集中任意两个节点之间没有边直接相连，且子集中节点的权重之和最大。

在一般图中，最大独立集是NP难问题，但在树结构上却可以通过动态规划在多项式时间内求解——这正是树形DP的魅力所在。

状态设计

对于树中的每个节点u，定义两个状态：

dp[u][0]：不选节点u时，以u为根的子树能获得的最大权重
dp[u][1]：选节点u时，以u为根的子树能获得的最大权重

状态转移

若不选u：子节点可选可不选，取最大值之和
dp[u][0] = Σ max(dp[v][0], dp[v][1])
若选u：子节点一定不能选
dp[u][1] = weight[u] + Σ dp[v][0]

其中v遍历u的所有子节点。

Java实现

import java.util.*;

/**
 * 树的节点定义
 */
class TreeNode {
    int id;
    int weight;
    List<TreeNode> children;
    TreeNode parent;

    TreeNode(int id, int weight) {
        this.id = id;
        this.weight = weight;
        this.children = new ArrayList<>();
        this.parent = null;
    }

    void addChild(TreeNode child) {
        children.add(child);
        child.parent = this;
    }
}

/**
 * 树形DP求解器
 * 支持：最大独立集、最小顶点覆盖、最大权独立集、树的路径统计
 */
public class TreeDP {

    /**
     * 树的最大独立集（无权版本：每个节点权重为1）
     * 返回dp数组，dp[u][0/1]表示u不选/选时的最大独立集大小
     */
    public int[][] maxIndependentSet(TreeNode root) {
        int n = countNodes(root);
        int[][] dp = new int[n + 1][2];
        dfsIndependentSet(root, dp);
        return dp;
    }

    private void dfsIndependentSet(TreeNode node, int[][] dp) {
        if (node == null) return;
        // 初始化：选当前节点至少包含自身
        dp[node.id][1] = node.weight;
        dp[node.id][0] = 0;

        for (TreeNode child : node.children) {
            dfsIndependentSet(child, dp);
            // 不选当前节点：子节点可选可不选
            dp[node.id][0] += Math.max(dp[child.id][0], dp[child.id][1]);
            // 选当前节点：子节点一定不能选
            dp[node.id][1] += dp[child.id][0];
        }
    }

    /**
     * 树的最小顶点覆盖（Minimum Vertex Cover）
     * 选择最少数量的节点，使得每条边至少有一个端点被选中
     */
    public int[][] minVertexCover(TreeNode root) {
        int n = countNodes(root);
        int[][] dp = new int[n + 1][2];
        dfsVertexCover(root, dp);
        return dp;
    }

    private void dfsVertexCover(TreeNode node, int[][] dp) {
        if (node == null) return;
        dp[node.id][0] = 0; // 不选当前节点
        dp[node.id][1] = 1; // 选当前节点

        for (TreeNode child : node.children) {
            dfsVertexCover(child, dp);
            // 不选当前节点：所有子节点必须选
            dp[node.id][0] += dp[child.id][1];
            // 选当前节点：子节点可选可不选
            dp[node.id][1] += Math.min(dp[child.id][0], dp[child.id][1]);
        }
    }

    /**
     * 树的最大权独立集（带权版本）
     */
    public int[][] maxWeightedIndependentSet(TreeNode root) {
        int n = countNodes(root);
        int[][] dp = new int[n + 1][2];
        dfsWeightedIndependentSet(root, dp);
        return dp;
    }

    private void dfsWeightedIndependentSet(TreeNode node, int[][] dp) {
        if (node == null) return;
        dp[node.id][0] = 0;
        dp[node.id][1] = node.weight;

        for (TreeNode child : node.children) {
            dfsWeightedIndependentSet(child, dp);
            dp[node.id][0] += Math.max(dp[child.id][0], dp[child.id][1]);
            dp[node.id][1] += dp[child.id][0];
        }
    }

    /**
     * 树的直径：树上最长路径的边数
     * 使用树形DP：对每个节点，维护经过该节点的最长路径
     */
    public int treeDiameter(TreeNode root) {
        int[] result = new int[]{0}; // 用数组传递引用
        dfsDiameter(root, result);
        return result[0];
    }

    private int dfsDiameter(TreeNode node, int[] globalMax) {
        if (node == null) return 0;
        if (node.children.isEmpty()) return 0;

        // 收集所有子树的最大深度
        List<Integer> depths = new ArrayList<>();
        for (TreeNode child : node.children) {
            depths.add(dfsDiameter(child, globalMax) + 1);
        }

        Collections.sort(depths, Collections.reverseOrder());
        if (depths.size() >= 2) {
            // 经过当前节点的最长路径 = 两个最深子树深度之和
            globalMax[0] = Math.max(globalMax[0], depths.get(0) + depths.get(1));
        } else if (depths.size() == 1) {
            globalMax[0] = Math.max(globalMax[0], depths.get(0));
        }
        return depths.get(0);
    }

    /**
     * 重建最大独立集的解：返回选中的节点ID列表
     */
    public List<Integer> reconstructIndependentSet(TreeNode root, int[][] dp) {
        List<Integer> selected = new ArrayList<>();
        reconstruct(root, dp, true, selected);
        return selected;
    }

    private void reconstruct(TreeNode node, int[][] dp, boolean canSelect, List<Integer> selected) {
        if (node == null) return;
        if (canSelect && dp[node.id][1] >= dp[node.id][0]) {
            selected.add(node.id);
            for (TreeNode child : node.children) {
                reconstruct(child, dp, false, selected); // 子节点不能选
            }
        } else {
            for (TreeNode child : node.children) {
                reconstruct(child, dp, true, selected); // 子节点可选
            }
        }
    }

    /**
     * 辅助方法：统计树的节点数量
     */
    private int countNodes(TreeNode root) {
        if (root == null) return 0;
        int count = 1;
        for (TreeNode child : root.children) {
            count += countNodes(child);
        }
        return count;
    }

    /**
     * 从边的列表构建有根树
     */
    public static TreeNode buildTree(int n, int[][] edges, int[] weights, int rootId) {
        TreeNode[] nodes = new TreeNode[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new TreeNode(i, weights[i]);
        }

        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }

        // BFS构建有根树
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(rootId);
        visited[rootId] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    nodes[u].addChild(nodes[v]);
                    queue.add(v);
                }
            }
        }
        return nodes[rootId];
    }

    public static void main(String[] args) {
        // 构建示例树：
        //        1(10)
        //       / | \
        //    2(5) 3(8) 4(3)
        //    /     |
        //  5(7)   6(2)
        int n = 6;
        int[][] edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 6}};
        int[] weights = {0, 10, 5, 8, 3, 7, 2};
        TreeNode root = buildTree(n, edges, weights, 1);

        TreeDP solver = new TreeDP();

        // 最大权独立集
        int[][] mis = solver.maxWeightedIndependentSet(root);
        System.out.println("最大权独立集大小: " + Math.max(mis[1][0], mis[1][1]));
        System.out.println("选中的节点: " + solver.reconstructIndependentSet(root, mis));

        // 最小顶点覆盖
        int[][] mvc = solver.minVertexCover(root);
        System.out.println("最小顶点覆盖大小: " + Math.min(mvc[1][0], mvc[1][1]));

        // 树的直径
        System.out.println("树的直径(边数): " + solver.treeDiameter(root));
    }
}

进阶：树形DP与背包结合

当每个节点包含一组”物品”，需要在树上做背包决策时，可以将子树的DP结果视为物品组进行合并。

/**
 * 树形背包：在子树中选择最多k个节点，使权重和最大
 */
public int[][] treeKnapsack(TreeNode root, int k) {
    int n = countNodes(root);
    int[][] dp = new int[n + 1][k + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    dfsKnapsack(root, k, dp);
    return dp;
}

private void dfsKnapsack(TreeNode node, int k, int[][] dp) {
    if (node == null) return;
    // 初始化：不选任何节点时价值为0
    for (int i = 0; i <= k; i++) dp[node.id][i] = 0;
    // 选当前节点至少占1个名额
    if (k >= 1) dp[node.id][1] = node.weight;

    for (TreeNode child : node.children) {
        dfsKnapsack(child, k, dp);
        // 倒序合并子树（01背包思想）
        for (int j = k; j >= 1; j--) {
            for (int c = 0; c <= j - 1; c++) {
                dp[node.id][j] = Math.max(dp[node.id][j],
                    dp[node.id][j - c] + dp[child.id][c]);
            }
        }
    }
}

复杂度分析

时间复杂度：每个节点被访问一次，每个状态转移遍历所有子节点，总时间O(N)，其中N为节点数。
空间复杂度：DP数组O(N)，递归栈深度最坏O(N)（链状树）。
树形背包：时间O(N × K²)，其中K为背包容量，通过优化可降至O(N × K)。

与其他算法的关联

树链剖分：当需要在路径上做DP时，树链剖分将树分解为链，配合线段树实现路径查询。
点分治：处理”经过某点的路径”类问题时，点分治将树分治为更小的子树。
换根DP：当根不固定时，先任选一个根做一遍DP，再通过第二次DFS换根计算所有根的情况。

总结

树形DP的精髓在于”子树独立性”：以某节点为根的子树的决策，只依赖于该节点与其直接子节点，而与树的其他部分无关。通过递归后序遍历，自底向上合并子问题，即可在O(N)时间内解决看似复杂的树上优化问题。本文以最大独立集为主线，展示了状态设计、转移方程、解重建的完整流程，并延伸到最小顶点覆盖、树直径、树形背包等变体。掌握树形DP后，读者可进一步挑战换根DP、树链剖分等更高级的树上算法。

Tagged with: Java 动态规划最大独立集最小顶点覆盖树形DP 树的直径树结构背包问题