树形动态规划是在属性结构上实现的动态规划，也称树形DP。动态规划自身是多阶段决策问题，而树形结构有明显的层次性，正好对应动态规划的多个阶段。树形结构有明显的层次性，正好对应动态规划的多个阶段。树形DP的求解过程一般为自底向上，将子树从小到大作为DP的“阶段”，将节点编号作为DP状态的第1维，代表以该节点为根的子树。树形DP一般采用深度优先遍历的方法，递归求解每颗子树，回溯时从子节点向上进行状态转移。在当前节点的所有子树都求解完毕后，才可以求解当前节点。
树形动态规划-01.png
树形DP有两种（大部分情况不可以相互转化）：
- 根到叶子：不过这种动态规划在实际的问题中运用的不多。
- 叶子到根：根的子节点传递有用的信息给根，完后根得出最优解的过程。
叶子到根节点
每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1 表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：
- 开关 1：切换当前节点的灯的状态；
- 开关 2：切换以当前节点为根的子树中，所有节点上的灯的状态；
- 开关 3：切换当前节点及其左右子节点（若存在的话）上的灯的状态；
需要找到最少的开关更新次数。
求解过程：用长度为2的二进制数来表示树的状态，低位表示根节点，高位表示除根以外的节点，其中00为全关，01为根节点开、其他全关，10为根节点关、其他全开，11为全开。用长度为3的二进制数来表示操作状态，从低位到高位分别表示操作1、2、3，一共8种状态。其执行操作后转移的条件为左右子树同时满足全开或者全关。
使用二进制进行状态压缩的好处是切换开关状态只需要使用异或。
