以前每次看见dp都是直接跳过，今天遇到了一道用概率dp求期望，仔细一想发现其实还是不难的。（不过要是想我理解什么是期望数……这辈子还是算了吧）
先有要挪用在别人blog看到的一段话：一般求概率DP或者是递推的问题，都是正着推，从初始状态往结束状态（结束状态一般是此类题要求的状态）推，所以先得到（或者说先已知）的是靠近初始状态的状态，所以想要求的当前状态是由可转移到此状态的前N可能个状态推过来的；而一般求期望DP，都是逆着推，从结束状态往初始状态（初始状态往往是此类题要求的状态）推，所以先得到（或者说先已知）的是靠近结束状态的状态，所以想要求的当前状态是由此状态对应接下来的N可能个状态推过来的。这边重点强调的是在求期望或者概率的时候到底是正推还是逆推。
没想到研究了两个多小时无果，留坑待填，题目为POJ2096,HDU4405,HDU3853
开大坑了，基本的dp还没学会，看来没几个月是填不上了。。。
热评文章