树状DP整理

什么是树状DP

建立在 ”树“ 这一数据结构上的DP问题，难度介于线性dp和图dp之间，当前节点的状态可能取决于父亲节点或者孩子节点，即存在两种状态转移方向，树可能包括二叉树和多叉树。

难点还是如何找到状态转移方程

主要题目类型

最大独立子集合问题

给一无向图，找出一个点集，使得任意两点之间都没有连边，这个点集就是独立集。而点最多的独立集，就是最大独立集，针对不问题，选取点的条件可能发生变化，但总体还是在限定条件下，选择最优的点集
最小点覆盖
最小支配集

典型例题

1. 最大独立子集合问题-洛谷P1352 没有上司的舞会

每个节点均有两个状态，当前节点参加和当前节点不参加的最优解，状态转移公式如下

$dp_{in}[parent] = dp_{out}[child_1] + dp_{out}[child_1]+...+dp_{out}[child_n]$

如果选取父节点，孩子节点不能选取

$dp_{out}[parent] = max(dp_{out}[child_1],dp_{in}[child_1]) + ...+max(dp_{out}[child_n],dp_{in}[child_n])$

如果不选取父节点，子节点可选可不不选，本题选择两者较大

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Main {
    static class TreeNode{
        List<TreeNode> children;
        int happiness;
        TreeNode(int happiness){
            this.children = new ArrayList<>();
            this.happiness = happiness;
        }
    }
    public static int[] dfs(TreeNode cur){
        //选择当前节点与不选择当前节点两种解
        int[] totalHappiness = new int[2];
        totalHappiness[0] = cur.happiness;

        int[] childHappiness;
        for(TreeNode child:cur.children){
            childHappiness = dfs(child);
            //父亲选了，孩子不能选
            totalHappiness[0] += childHappiness[1];
            //父亲没选，孩子可选可不选
            totalHappiness[1] += Math.max(childHappiness[0],childHappiness[1]);
        }
        return totalHappiness;
    }

    public static void main(String[] args) {
		//建立二叉树的过程省略
        //....
        //dfs遍历
        int[] result = dfs(root);
        System.out.println(Math.max(result[0], result[1]));
    }
}

2. 洛谷P2015 二叉苹果树

假设求节点 $i$ 保留 $j$ 条边的最优情况，其状态转移公式如下

$dp[i][j] = max(dp[i][j], dp[u][i - k - 1] + dp[v][k] + weight[i][v])$

其中 $v$ 为当前节点的某个子节点， $weight[i][v]$ 为连接子节点的遍历的权重，需要遍历所有子节点以及所有保留边情况，计算得到当前节点的所有候选状态。

难理解的几个点

为什么状态转移是 $dp[u][i - k - 1] + dp[v][k] + weight[i][v]$
- 我们通常理解的二叉树或者多叉树的子问题划分，一定是将保留的边分配给所有的子节点，看每个子节点最最优情况，最后求和为当前节点最优情况，以二叉树为例子，即 $dp[left][i - k - 1] + dp[right][k] + weight[left][v] + + weight[right][v]$
- 该状态转移公式，并不从所有的子节点出发，而是将保留的边分配给当前已遍历的子节点，即默认未遍历子树中的边全部删除情况，每遍历到一个新的孩子节点，重新考虑当前子节点分配边的情况
- 形象的例子就是，分苹果给张三、李四、王五，第一种思路是直接把三个人叫过来，看如何分成三份；另一种是先把张三叫过来，记录下来把苹果从 0-全部给他的情况，再叫李四，看给张三后，剩下不同苹果的基础上，给李四 0-全部的最优情况。最后把王五拉过来，看给张三李四分完剩下，给他分怎么最优。
即一种是直接考虑所有的节点之间分配，另一种是分成已遍历 + 未遍历，未遍历节点不断地加入已遍历集合。第二种思路适用范围更广，如果问题变为多叉或者不定叉树，第一种思路代码无法实现

遍历部分的实现，为什么要倒序DP，即保留边数从大到小

第一层遍历，遍历当前节点保留不同边的情况，最大边数 $j$ 取已遍历子节点子树中边的个数和与要求保留边个数的较小值，倒序DP
第二层遍历，遍历当前新节点的所有保留边数情况，最大边数 $k$ 取 $j-1$ 与 当前子节点子树边数的较小值，顺序无所谓

划分为子问题后，需要与原数组的前部元素求和，所以求大时会用到小，如果正序，前部修改导致后部计算使用的新计算的状态

for(int j = Math.min(childEdges[curNode], m);j >= 1;j--){
    //k为当前子节点中保留边的个数
    for(int k = Math.min(j - 1, childEdges[i]);k >= 0;k--){
        dpArray[curNode][j] = Math.max(dpArray[curNode][j], dpArray[curNode][j - k - 1] + dpArray[i][k] + adjustMatrix[curNode][i]);
    }
}

代码

基于dfs+邻接矩阵实现

import java.util.Scanner;
class Main {
    public static void dfs(int curNode, int[][] adjustMatrix,int[][] dpArray,int[] childEdges, int[] visited, int m){
        visited[curNode] = 1;
        //首先dfs子树，求子问题解并获得子结点个数
        for(int i = 0;i < adjustMatrix.length;i++){
            if(adjustMatrix[curNode][i] != -1 && visited[i] != 1){
                visited[i] = 1;
                dfs(i, adjustMatrix, dpArray, childEdges, visited, m);
                //已遍历子树边数和
                childEdges[curNode] += childEdges[i] + 1;
                //遍历当前节点保留不同数量树枝的解
                for(int j = Math.min(childEdges[curNode], m);j >= 1;j--){
                    //k为当前子节点中保留边的个数
                    for(int k = Math.min(j - 1, childEdges[i]);k >= 0;k--){
                        dpArray[curNode][j] = Math.max(dpArray[curNode][j], dpArray[curNode][j - k - 1] + dpArray[i][k] + adjustMatrix[curNode][i]);
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 节点和边的数量
        int m,n;
        int[][] adjustMatrix;
        m = scanner.nextInt();
        n = scanner.nextInt();
        adjustMatrix = new int[m][m];
        //初始化矩阵
        for(int i = 0;i < m;i++){
            for(int j = 0;j < m;j++){
                adjustMatrix[i][j] = -1;
            }
        }
        //读取边
        int tempNode1;
        int tempNode2;
        int tempWeight;
        for(int i = 0;i < m - 1;i++){
            tempNode1 = scanner.nextInt() - 1;
            tempNode2 = scanner.nextInt() - 1;
            tempWeight = scanner.nextInt();
            adjustMatrix[tempNode1][tempNode2] = tempWeight;
            adjustMatrix[tempNode2][tempNode1] = tempWeight;
        }
        //dfs动态规划
        int[] visited = new int[m];
        int[] childEdges = new int[m];
        int[][] dpArray = new int[m][n + 1];
        dfs(0, adjustMatrix, dpArray, childEdges, visited, n);
        System.out.println(dpArray[0][n]);
    }
}