概率DP主要用于求解期望、概率等题目。
转移方程有时候比较灵活。
一般求概率是正推，求期望是逆推。通过题目可以体会到这点。
poj2096:Collecting Bugs
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef long long ll;
using namespace std;
#define mod 1000000007
double dp[1010][1010];
int n,s;
int main()
{
while(scanf("%d%d",&n,&s)!=EOF)
{
dp[n][s]=0;
for(int i=n;i>=0;i--)
{
for(int j=s;j>=0;j--)
{
if(i==n&&j==s) continue;
dp[i][j]=(n*s+i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1])/(n*s-i*j);
}
}
printf("%.4f\n",dp[0][0]);
}
return 0;
}
//sdut2626题目： The number of steps
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef long long ll;
using namespace std;
#define mod 1000000007
int n;
double dp[110][110];
double a,b,c,d,e;
int main()
{
while(scanf("%d",&n)!=EOF&&n!=0)
{
scanf("%lf%lf",&a,&b);
scanf("%lf%lf%lf",&c,&d,&e);
memset(dp,0,sizeof(dp));
dp[n][1]=0;
for(int i=2;i<=n;i++)
{
dp[n][i]=dp[n][i-1]+1;
}
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
if(j==1)
{
if(i==n) continue;
dp[i][j]=dp[i+1][j]*a+dp[i+1][j+1]*b+1.0;
}
else
{
dp[i][j]=dp[i][j-1]*e+dp[i+1][j]*c+dp[i+1][j+1]*d+1.0;
}
}
}
printf("%.2lf\n",dp[1][1]);
}
return 0;
}HDU4405：
题目大意：
跳棋有0~n个格子，每个格子X可以摇一次色子，色子有六面p(1=<p<=6),概率相等，可以走到X+p的位置，有些格子不需要摇色子就可以直接飞过去。问从0出发到达n或超过n摇色子的次数的期望。
解题思路：
dp[i]表示从i出发到达最终位置的次数期望。
转移方程当i需要摇色子时，dp[i]=Σ(1+dp[i+j])(1<=j<=6);否则dp[i]=dp[jump[i]] 表示从i能够跳得到的最大位置。
预处理后面的6个位置，直接转移就行。
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m;
int path[100010];
double dp[100010];
int main()
{
int xx,yy;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
memset(path,-1,sizeof(path));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&xx,&yy);
path[xx]=yy;
}
for(int i=n;i>=1;i--)
{
if(path[i]!=-1)
{
int j=path[i];
if(path[j]!=-1)
path[i]=path[j];
else path[i]=j;
}
}
for(int i=0;i<6;i++)
dp[n+i]=0;
for(int i=n-1;i>=0;i--)
{
if(path[i]!=-1)
dp[i]=dp[path[i]];
else
{
double tt=0;
for(int j=1;j<=6;j++)
{
tt+=dp[i+j]*(1.0/6.0);
}
dp[i]=1+tt;
}
}
printf("%.4f\n",dp[0]);
}
return 0;
}
