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