本文主要是介绍概率DP总结 by kuangbin，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html
概率DP主要用于求解期望、概率等题目。
转移方程有时候比较灵活。
一般求概率是正推，求期望是逆推。通过题目可以体会到这点。
首先先推荐几篇参考的论文：
《信息学竞赛中概率问题求解初探》
《浅析竞赛中一类数学期望问题的解决方法》
《有关概率和期望问题的研究 》
1、POJ 3744
POJ 3744
2、POJ 2096 Collecting Bugs
dp求期望，概率dp入门题。很简单，题解见here
POJ 2096
3、ZOJ 3329 One Person Game
此题的递推方程稍微复杂点，需要转化后求解系数。
题意：有三个骰子，分别有k1,k2,k3个面。
每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。
当分数大于n时结束。求游戏的期望步数。初始分数为0
题解见here
ZOJ 3329
4、HDU 4405 Aeroplane chess
这题是2012年网络赛的题目。是很简单的概率dp.转移方程很好想到。
求期望。按照公式从后望前递推就可以得到答案了。
解题报告here
HDU 4405
5、HDU 4089 Activation
这题是求概率，但是也有种求期望的感觉，都是要列出公式来，化简，递推出答案。
2011年北京现场赛的题目。再比赛时做出来确实不容易，需要对概率DP很熟悉才能做出来。
解题报告见here
HDU 4089
6、HDU 4035 Maze
经典的的概率DP的题目。做了可以体会到dp 求期望的一类的方法。
解题报告见here
HDU 4035
7、HDU 3853 LOOPS
比较简单的概率DP了，入门基础题。
注意一个小陷进。
解题报告here
HDU 3853
8、POJ 2151 Check the difficulty of problems
此题还不算是概率DP的题目。就是DP题，求概率。
想到转移方程就不难了。
题解见here
POJ 2151
9、Codeforces 148D Bag of mice
抓老鼠问题。转移方程要思考下就出来了。
解题报告here
CF 148D
10、POJ 3071 Football
足球赛的淘汰赛问题。问最后胜利的概率最大的球队。
简单概率DP
题解报告见here
POJ 3071
11、SGU 495 Kids and Prizes
简单的概率DP。 O（1）,推公式就可以出来。
解题报告here
SGU 495
12、ZOJ 3380 Patchouli's Spell Cards
用JAVA的大树做的概率DP。有m个位置，每个位置填入1~n中的一个数，求至少有L个数一样的概率。
解题报告见here
ZOJ 3380
13、ZOJ 3640 Help Me Escape
比较简单的概率DP，记忆化搜索很好理解，也很容易写。
解题报告here
ZOJ 3640
14、HDU 4336 Card Collector
求期望，可以状态压缩概率DP求解。也可以用容斥原理直接求。解题报告here
HDU 4336 HDU 4336
下面介绍的三题是用高斯消元法求解的概率DP
15、ZJUT 1423 地下迷宫
一个N*M的迷宫，除了障碍外等概率走，求起点走到终点步数的期望。先在起点进行bfs，找出所以可以到达的点并编号，然后建立方程组求解。
ZJUT 1423
16、ZJUT 1317 掷飞盘
在一个环上抛掷两个飞盘 ，每个飞盘等概率往左和右走，问两个飞盘走到同一个地方所需要步数的期望。
按照他们的距离表示状态进行概率DP。dp[i]=dp[i-2]/4+dp[i+2]/4+dp[i]/2+1.整理下就出来方程。注意是循环的，要进行处理。
ZJUT 1317
17、HDU 4418 Time travel
在坐标轴上用高斯消元法求解。注意N=1的时候要特判一下。解题报告here
HDU 4418
这篇关于概率DP总结 by kuangbin的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
