首页 > 代码库 > 概率DP——求期望

概率DP——求期望

  一般求期望类题目都是倒着来做的,dp[i]表示i状态下要达到要求状态的期望值,于是dp[0]就是我们要找的答案,我们可以通过此来推状态转移方程,可以得到dp[i]=Σ(dp[k>i]*p[k])+ 1,由于由k状态转移到i状态会多一步操作,这多的一步乘以每种概率再求和刚好等于1,所以转移公式后面有一个加一。

 

POJ 2096
题目链接:http://poj.org/problem?id=2096

一个软件有s个子系统,会产生n种bug
某人一天发现一个bug,这个bug属于一个子系统,属于一个分类
每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n
问发现n种bug,每个子系统都发现bug的天数的期望。

dp[i][j]表示已经找到了i种bug,j个系统的bug的情况下要达到要求的天数的期望,
dp[i>=n][j>=s]=0,答案就是dp[0][0],于是dp[i][j]可以转化为以下四种情况:
1、发现一个bug存在于已有系统和bug,dp[i][j],概率(i*j)/(n*s);
2、发现一个bug存在于已有bug,未知系统,dp[i][j+1],概率i*(s-j)/(n*s);
3、发现一个bug存在于已有系统,未知bug,dp[i+1][j],概率(n-i)*j/(n*s);
4、发现一个bug全都是未知,dp[i+1][j+1],概率(n-i)*(s-j)/(n*s);
于是可以得到状态转移方程(经化简)dp[i][j]=(dp[i+1][j+1]*(n-i)*(s-j)+dp[i+1][j]*(n-i)*j+dp[i][j+1]*i*(s-j)+n*s)/(n*s-i*j);

 1 //#include<bits/stdc++.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 double dp[1010][1010];
 6 int main()
 7 {
 8     int n,s;
 9     while(~scanf("%d%d",&n,&s))
10     {
11         memset(dp,0,sizeof(dp));
12         for(int i=n;i>=0;i--)
13             for(int j=s;j>=0;j--)
14                 if(i!=n||j!=s)
15                     dp[i][j]=(dp[i+1][j+1]*(n-i)*(s-j)+dp[i+1][j]*(n-i)*j+dp[i][j+1]*i*(s-j)+n*s)/(n*s-i*j);
16         printf("%.4f\n",dp[0][0]);
17     }
18     return 0;
19 }

 

ZOJ 3329
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3329

有三个骰子,分别有k1,k2,k3个面。
每次掷骰子,如果三个面分别为a,b,c则分数置0,否则加上三个骰子的分数之和。
当分数大于n时结束。求游戏的期望步数。初始分数为0

dp[i]表示在i分数的情况下要达到要求的期望,于是可以很简单推导出状态转移方程dp[i]=Σ(p[k]*dp[i+k])+dp[0]*p[0]+1;
所有的dp[i]都和dp[0]有关,而且dp[0]就是我们要求的答案,于是可以变形为dp[i]=a[i]*dp[0]+b[i],
所以dp[i]=Σ(p[k]*(a[i+k]*dp[0]+b[i+k]))+dp[0]*p[0]+1
             =(Σp[k]*a[i+k]+p[0])*dp[0]+Σp[k]*b[i+k]+1;
最后可以得到dp[0]=a[0]*dp[0]+b[0],dp[0]=b[0]/(1-a[0]);

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 double p[20];
 4 int main()
 5 {
 6     int t;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         memset(p,0,sizeof(p));
11         int n,k1,k2,k3,A,B,C;
12         scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&A,&B,&C);
13         p[0]=1.0/(double)(k1*k2*k3);
14         for(int i=1;i<=k1;i++)
15             for(int j=1;j<=k2;j++)
16                 for(int k=1;k<=k3;k++)
17                     if(i!=A||j!=B||k!=C)
18                         p[i+j+k]+=p[0];
19         double a[510]={0},b[510]={0};
20         for(int i=n;i>=0;i--)
21         {
22             for(int j=3;j<=k1+k2+k3;j++)
23             {
24                 a[i]+=a[i+j]*p[j];
25                 b[i]+=b[i+j]*p[j];
26             }
27             a[i]+=p[0];
28             b[i]+=1.0;
29         }
30         printf("%.15lf\n",b[0]/(1-a[0]));
31     }
32     return 0;
33 }

 

概率DP——求期望