概率DP主要用于求解期望、概率等题目。
转移方程有时候比较灵活。
一般求概率是正推，求期望是逆推。通过题目可以体会到这点。
poj2096:
#include#include #include #include #include typedef long long ll;using namespace std;#define mod 1000000007double 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;}//http://www.cnblogs.com/jackge/archive/2013/05/21/3091757.html
sdut2626题目：
#include#include #include #include #include typedef long long ll;using namespace std;#define mod 1000000007int 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#include #include #include #include #include #include #include #define inf 0x3f3f3f3ftypedef 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;}