DP 树的最小支配集，最小点覆盖与最大独立集

在图论中，树的最小支配集（Minimum Dominating Set）、最小点覆盖（Minimum Vertex Cover）和最大独立集（Maximum Independent Set）是经典的问题，可以使用动态规划来解决。下面是使用动态规划求解这些问题的Java代码示例：

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

class TreeNode {
    int val;
    List<TreeNode> children;

    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

public class TreeProblems {

    // 最小支配集问题
    public static int minDominatingSet(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int take = 1;
        int notTake = 0;
        
        for (TreeNode child : root.children) {
            take += minDominatingSet(child);
            for (TreeNode grandchild : child.children) {
                notTake += minDominatingSet(grandchild);
            }
        }
        
        return Math.min(take, notTake);
    }

    // 最小点覆盖问题
    public static int minVertexCover(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int take = 1;
        int notTake = 0;

        for (TreeNode child : root.children) {
            take += minVertexCover(child);
            notTake += child.children.size() > 0 ? minVertexCover(child.children.get(0)) : 0;
        }

        return Math.min(take, notTake);
    }

    // 最大独立集问题
    public static int maxIndependentSet(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int take = 1;
        int notTake = 0;

        for (TreeNode child : root.children) {
            take += maxIndependentSet(child);
            for (TreeNode grandchild : child.children) {
                notTake += maxIndependentSet(grandchild);
            }
        }

        return Math.max(take, notTake);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode child1 = new TreeNode(2);
        TreeNode child2 = new TreeNode(3);
        TreeNode child3 = new TreeNode(4);
        
        root.children.add(child1);
        root.children.add(child2);
        root.children.add(child3);
        
        TreeNode grandchild1 = new TreeNode(5);
        TreeNode grandchild2 = new TreeNode(6);
        
        child1.children.add(grandchild1);
        child2.children.add(grandchild2);

        System.out.println("Minimum Dominating Set: " + minDominatingSet(root));
        System.out.println("Minimum Vertex Cover: " + minVertexCover(root));
        System.out.println("Maximum Independent Set: " + maxIndependentSet(root));
    }
}

在这个示例中，我们定义了一个简单的树结构（TreeNode），并使用动态规划方法解决了最小支配集、最小点覆盖和最大独立集问题。每个问题都是通过递归计算来实现的。请注意，实际应用中的树结构可能会更加复杂，代码也会相应地调整。