@山哥@SYC
balabala什么叫循环DP呢~~ 所谓循(zui)环(duan)DP(lu)，就是一种山哥发明的DP方式，能解决带后效性的DP问题~~
感觉好高大上啊！！跪求如何进行循环DP~
图论是很基础的一项内容，我们把目光从DP转向图论，哦不，把DP以图论的方式思考：
把每个状态看成一个点，如果状态i可以转移到状态j，那么就把i向j连一条有向边，if转移存在代价，那么就给边附上权值……
是不是很简单。。于是很显然，如果是无后效性DP那么构成的图一定是DAG
于是我们的DP问题就成了单（多）源最短路= =|||
如果DP存在后效性。。那么这个图会存在环，但众所周知，最短路是可以处理环的情况。。
于是就可以对着由DP构出的图跑SPFA或DIJ。。后效性神马的，谁管它
狗狗：“环给你玩~”
涛爷：“你有环可以，但不要影响我的DP！”
好了。。现在不会影响了= =|||
关于循环DP的复杂度问题，时间复杂度就是你跑DIJ或SPFA的复杂度，空间复杂度也一样
相对于DP比起来，DP的复杂度都要更优，但是啊，循环DP能解决涛爷的问题哦~
loading...
评论 (0)
