数据结构与算法_线性DP和树形DP

    具有线性阶段划分的动态规划算法统称为线性动态规划（简称线性 DP）。如果状态包含多个维度，每个维度都是线性变化的阶段，也称为线性 DP。

    在树形结构上（非线性结构）实现的动态规划称为树形DP。

    动态规划本身是多阶段决策问题，而树形结构具有明显的层次性，正好对应动态规划的多阶段性。树形DP一般自底向上，将子树从小到大的顺序作为 DP的 “阶段”，将结点编号作为DP状态的第一维，代表以该结点为根的子树。树形 DP 一般采用深度优先遍历，递归求解每棵子树，回溯时从子结点向上进行状态转移。当前结点的所有子树求解完毕，才可以求解当前结点。