浅谈 dp 与 DAG 的关系
最近做了好几道跟 DAG 有关的题，发现许多都和 dp 有关，经过一番思考， 想到一些东西，在这里记录下来。
首先是 dp 的定义: 通过定义状态和状态间的关系， 拆分子问题去求解最优解。
拆分子问题实质上是一个递归的过程，类似于分治
如果把状态和状态间的转移关系看成一张有向图 G 的话，那么拆分问题的过程 实质上是在 G 上进行 dfs
如果 G 不是 DAG 的话，那么 G 中就会有一个环 (就像下面这个图)
在 G 中进行 dfs 时，假如从 1 开始 dfs, 那么遍历到 3 时，3 的最优解要由 1 决定， 而 1 的最优解还未求得，导致答案错误。
所以根据状态和状态转移关系定义的图一定要是一个 DAG, 否则无法通过 dp 求解