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