所谓概率dp，用动态规划的思想找到一个事件中可能发生的所有情况，然后找到符合要求的那些情况数，除以总数便可以得到符合要求的事件发生的概率。其核心思想还是通过dp来得到事件发生的所有情况，很类似在背包专题中我们提及的组合记数问题。
我们通过具体的实例来体会概率dp这类问题。(Problem source : Light OJ 1064)
Description
n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x?
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each test case contains two integers n (1 ≤ n < 25) and x (0 ≤ x < 150). The meanings of n and x are given in the problem statement.
Output
For each case, output the case number and the probability in 'p/q' form where p and q are relatively prime. If q equals 1 then print p only.
题目大意：给出整数n、x，同时抛掷n个筛子，求解点数和大于x情况出现的概率。
数理分析：我们更加细化的模拟这个抛掷筛子的过程，从第一个开始抛掷，不难发现有6种情况，然后抛掷第二个筛子，基于第一个筛子的6种情况，我们可以得到抛完第二个筛子后所有的情况，然后抛掷第三个筛子……
我们设置二维数组dp[i][j]表示抛掷i个筛子后，点数为j的情况数，我们容易得到如下的状态转移方程：
dp[i][j] = dp[i-1][j-k] (k∈[1,6])
基于这个状态转移方程，我们不难得到第n个筛子抛掷后所有可能的情况的总数和符合要求的总数，这里根据题目的输出要求，需要是分数的最简形式，我们只需调用欧几里得算法求出最大公约数然后化简即可，而对于概率为0和1的特殊情况，设置条件进行判断即可。
参考代码如下。
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; long long n , m , dp[][]; long long gcd(long long a , long long b)
{
return b == ? a:gcd(b,a%b);
} int main()
{
int i , j , k , cas , T;
scanf("%d",&T);
for(cas = ;cas <= T;cas++)
{
scanf("%lld%lld",&n,&m);
memset(dp , , sizeof(dp));
dp[][] = ;
for(i = ;i <= n;i++)
{
for(j = ;j < ;j++)
{
for(k = ;k <= && j-k >= ;k++)
dp[i][j] += dp[i-][j-k];
}
}
long long p , q , g;
q = p = ;
for(int i = ;i < ;i++)
{
p += dp[n][i];
if(i >= m)
q += dp[n][i];
}
g = gcd(p , q);
p/=g;
q/=g;
printf("Case %d: ",cas);
if(q == ) printf("0\n");
else if (q == p) printf("1\n");
else {printf("%lld/%lld\n",q,p);}
}
}