3
16
2015
0

【口胡向】循环DP

@山哥@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...

Category: 算法 | Tags: | Read Count: 18382

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com