【动态规划4】树与图上的动态规划

对应进阶篇第 16 章。 树与图上的动态规划，顾名思义，就是以树或图为模型的动态规划。树上动态规划是最常见 的动态规划形式之一，因为树型本身就带来了子结构（树上的父子关系），大部分情况下，都是 通过子结点的 DP 值推导出父结点的 DP 值。而图上的动态规划，由于没有很明显的子结构，所 以比较受限。有向无环图（DAG）由于点之间有着明显的分层，性质相较于图更加良好。许多图 上的问题可能转化后成为树上的或 DAG 上的问题。剩下的许多问题模型，又可以转化为最短路 问题。我们将依次介绍上述提到的模型。