概率DP求期望大多数都是全期望公式的运用。主要思考状态空间的划分以及状态事件发生的概率。问题可以分为无环和有环两类。无环一类多数比较简单，可以通过迭代或者记忆化搜索完成。有环一类略复杂，可以通过假设方程化简公式解决或者高斯消元求解。
POJ 2096 Collecting Bugs
http://poj.org/problem?id=2096
概率DP入门题，注意理解和状态的转移过程才能建立方程。
dp[i][j]表示已经找到i种系统的j种bug时达到目标状态时的期望，此时找到一个bug，可能仍属于原来i种系统j种bug，也可能是第i+1种系统j种bug，也可能是i种系统第j+1种bug，也可能是第i+1种系统第j+1种bug，不同情况有不同的概率。这是所谓的马尔柯夫过程。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
][];
][];
double r;
int n,s;
double dp(int i,int j)
{
if(vis[i][j]||i>n||j>s) return f[i][j];
vis[i][j]=true;
f[i][j]=+(n-i)*j/r*dp(i+,j)+i*(s-j)/r*dp(i,j+)+(n-i)*(s-j)/r*dp(i+,j+);
f[i][j]/=(-i*j/r);
return f[i][j];
}
int main()
{
scanf("%d%d",&n,&s);
r=n*s;
vis[n][s]=;
f[n][s]=;
printf(,));
;
}
UVa 11762 Race to 1
概率DP，马尔柯夫过程。
dp[i]表示i经过题目变换得到1的期望，这样dp[i]=(s[i]-p[i])/s[i]*dp[i]+sum{1/s[i]*dp[i/prime[i][j]]}其中s[i]表示1到i之间的素数个数，p[i]表示数字i
的质因子个数，prime[i][j]表示数字i的第j个质因子。
终止条件是dp[1]=0。因为1不需要变化就能得到1，所以期望的步骤数是0。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxn 1000000
using namespace std;
];
];
vector<];
void init()
{
memset(is_prime,,sizeof(is_prime));
is_prime[]=;
; i<=maxn; ++i)
if(is_prime[i])
{
numb[i].push_back(i);
for(int j=i+i; j<=maxn; j+=i)
{
is_prime[j]=false;
numb[j].push_back(i);
}
}
; i<=maxn; ++i)
]+;
];
}
];
];
int n;
double dp(int x)
{
if(vis[x]) return f[x];
vis[x]=true;
f[x]=;
; i<numb[x].size(); ++i)
f[x]+=1.0/sum[x]*dp(x/numb[x][i]);
f[x]/=(-((sum[x]-numb[x].size())/1.0/sum[x]));
return f[x];
}
int main()
{
;
scanf("%d",&T);
f[]=;
vis[]=;
init();
while(T--)
{
scanf("%d",&n);
printf("Case %d: %.10lf\n",++kase,dp(n));
}
;
}
简单的概率DP，注意用记忆化搜索会爆栈。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,m;
];
],p;
int main()
{
p=/6.0;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m) break;
memset(move,,sizeof(move));
; i<m; ++i)
{
int x,y;
scanf("%d%d",&x,&y);
move[x]=y;
}
memset(f,,sizeof(f));
; i>=; --i)
{
if(move[i]) f[i]=f[move[i]];
else
{
f[i]=;
; j<=; ++j)
f[i]+=p*f[i+j];
}
}
printf(]);
}
;
}
经典的简单概率DP，注意可能有到达自身概率是1的情况，这种地方不可能再达到别的地方，所以应该被忽略掉。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
][][];
][];
int n,m;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(pro,,sizeof(pro));
memset(dp,,sizeof(dp));
; i<=n; ++i)
; j<=m; ++j)
scanf(],&pro[i][j][],&pro[i][j][]);
; --i)
; --j)
{
if(i==n&&j==m) continue;
dp[i][j]=;
]==) dp[i][j]=;
else
{
dp[i][j]+=pro[i][j][]*dp[i][j+]+pro[i][j][]*dp[i+][j];
dp[i][j]/=(-pro[i][j][]);
}
}
printf(][]);
}
;
}
带环的概率DP。设dp[i]表示当前为i分时到结束游戏时的期望，这样dp[i]=r*dp[0]+∑pk*dp[i+x]。其中r表示第一二三个骰子分别取a，b，c时的概率即1/(k1*k2*k3)。pk表示三个骰子和为x时的概率。终止条件时i>=n时，dp[i]=0。我们的最终答案是dp[0],但是这里每次递推都需要用到dp[0],显然不符合动规的特点，是所谓有环。因此需要别的方法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
#define MAXN 30005
using namespace std;
],B[];
];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,k1,k2,k3,a,b,c;
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
double r=1.0/(k1*k2*k3);
memset(A,,sizeof(A));
memset(B,,sizeof(B));
memset(pro,,sizeof(pro));
; i<=k1; ++i)
; j<=k2; ++j)
; k<=k3; ++k)
if(!(i==a&&j==b&&k==c))
pro[i+j+k]+=r;
int s=k1+k2+k3;
; --i)
{
; j<=s; ++j)
{
A[i]+=pro[j]*A[i+j];
B[i]+=pro[j]*B[i+j];
}
A[i]+=r;
B[i]++;
}
printf(]/(-A[]));
}
;
}
ZOJ 3582 Back to the Past
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4624
概率DP求期望。dp[i][j]表示两侧分别亮了i和j个灯，然后枚举当天左右两侧分别亮的灯数，这里要注意求概率，比如左右两侧分别亮了k1、k2个灯，那么该事件发生的概率是
C[n-i][k1]*pow(p,k1)*pow(1-p,n-i-k1)*C[n-j][k2]*pow(p,k2)*pow(1-p,n-j-k2),注意这里选择亮的灯的部分。记忆化搜索或者递推都可以解决。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#define maxn 1000000
using namespace std;
int n,m;
double p;
][];
][],pro[][];
][];
void init()
{
pro[][]=pro[][]=;
; i<=*n; ++i)
{
pro[][i]=pro[][i-]*p;
pro[][i]=pro[][i-]*(-p);
}
}
double dp(int a,int b)
{
;
if(vis[a][b]) return f[a][b];
vis[a][b]=true;
f[a][b]=;
; i<=n-a; ++i)
; j<=n-b; ++j)
{
&&j==))
f[a][b]+=C[n-a][i]*pro[][i+j]*C[n-b][j]*pro[][n*-a-b-i-j]*dp(a+i,b+j);
}
f[a][b]/=(-pro[][n*-a-b]);
return f[a][b];
}
int main()
{
C[][]=;
; i<=; ++i)
{
C[i][]=C[i][i]=;
; j<i; ++j)
C[i][j]=C[i-][j]+C[i-][j-];
}
while(scanf("%d%d%lf",&n,&m,&p))
{
if(!n&&!m&&!p) break;
init();
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
printf(,));
}
;
}