浅谈 概率与期望 DP

时间：2022-07-03 15:03:33

概率与期望DP，一直都不会啊，感觉好难完全没法思考…

期望题一般是逆推，当然也有一些是顺推，然而现在我只做过一些水得很的期望题，好菜啊…

UVa 11021 麻球繁衍 蓝书p140

题解：

现在有k只麻球，每只麻球都只能活一天，但是可能会在死前爆出0到n-1值麻球，几率分别为 p0,p1,p2...pn−1 ，求m天后所有麻球都死了的概率，因为每只麻球是独立的，这只麻球并不会导致另一只麻球死掉，也不会让另一只麻球少生几个麻球，所以我们只需要管最开始有1只麻球，然后最后用乘法原理即可，也就是第一只麻球死完的概率乘以第二只麻球死完的概率一直乘到第k只麻球死完的概率，如果有没有死的那就不行了。
问题转化为一只麻球在m天死完的概率，于是我们发现，在第i天死完的几率为生一个蛋的几率乘以（这一个蛋在）第i-1天死完的几率+生两个蛋的几率乘以（整两个蛋）在第i-1天死完的几率，也就是一个蛋在i-1天死完的几率乘以一个蛋在i-1天死完的几率。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T,n,k,m;
const int MAXN=1000+10;
double p[MAXN],dp[MAXN];
double fast_pow(double num,int k){
double now=num;
double ans=1.0;
while(k){
if(k&1) ans*=now;
        now*=now;k>>=1;
    }
return ans;
}
int main(){scanf("%d",&T);
for(register int kase=1;kase<=T;kase++){
scanf("%d%d%d",&n,&k,&m);
for(register int i=0;i<=n-1;i++) scanf("%lf",&p[i]);
        dp[0]=0;dp[1]=p[0];
for(register int i=2;i<=m;i++){
            dp[i]=0;
for(register int j=0;j<=n-1;j++){
                dp[i]+=p[j]*pow(dp[i-1],j);
            }
        }
double ans=fast_pow(dp[m],k);
printf("Case #%d: %0.7lf\n",kase,ans);
    }
return 0;
}

浅谈 概率与期望 DP

UVa 11427 玩纸牌

这道题貌似很水，蓝书p141，我自己都写出来了，就是说我们要求的是一天晚上玩儿停了的概率，那么我们用1除以这个概率就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T,n,a,b;
double p,dp[110][110];
int main(){
scanf("%d",&T);
for(register int kase=1;kase<=T;kase++){
scanf("%d/%d %d",&a,&b,&n);
        p=(double)a/b;
memset(dp,0,sizeof(dp));
        dp[0][0]=1.0;dp[0][1]=0.0;//在地0局，赢0局的概率为1，在第0局，赢1局的概率为0 
for(register int i=1;i<=n;i++)
for(register int i=1;i<=n;i++){//一共玩儿的局数应该小于a/b，故j/i<=a/b，即j*b<=i*a 
for(register int j=0;j*b<=i*a;j++){
if(j==0){
                    dp[i][j]=dp[i-1][j]*(1.0-p);
continue;
                }
                dp[i][j]=dp[i-1][j]*(1.0-p)+dp[i-1][j-1]*p;
            }
        }
double ans=0.0;
for(register int j=0;j*b<=a*n;j++) 
            ans+=dp[n][j];
int final=floor(1/ans);
printf("Case #%d: %d\n",kase,final);
    }
return 0;
}

浅谈 概率与期望 DP

POJ 2096

题目大意：

现在有n种bug，有s个子系统，问期望多少次出现bug使得每个系统都有bug并且每个bug至少出现过一次，每次可以出现一种bug，出现概率均等，都为1/n，每次出现的位置（即位于哪个子系统）的概率也均等，都为1/s。

题解：

我们很容易想到用dp[i][j]表示现在的情况，i表示现在收集了n种bug，j表示现在出现在了j个系统中，显然dp[n][s]时，期望次数为0
显然dp[i][j]可以从dp[i][j],dp[i+1][j],dp[i][j+1],dp[i+1][j+1]转移过来，分别表示新出现的bug是旧bug并且出现在旧系统中，新出现的bug是新bug但是出现在旧系统中，新出现的bug之前已经出现过了但是这次出现在了新系统中，和新bug新系统，转移的概率很显然，我们把式子列出来之后移项，然后两边同时乘以一个n*s，可以化简运算，显然答案是dp[0][0]

#include<iostream>
#include<cstdio>
#include<cstring>
double dp[1010][1010];
int n,s;
int main(){
scanf("%d%d",&n,&s);//n个bug,s个系统
double ns=n*s;
    dp[n][s]=0.0;
for(register int i=n;i>=0;i--){
for(register int j=s;j>=0;j--){
if(i==n&&j==s) continue;
            dp[i][j]=(ns+((n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+i*(s-j)*dp[i][j+1]))/(ns-i*j);
        }
    } 
printf("%.4lf",dp[0][0]);
return 0;
}

浅谈 概率与期望 DP

期望的线性性

首先，什么是期望？期望就是指一个变量的平均值，当然是加权的，比如这个变量可能是1的概率为百分之五十，可能是2的概率为百分之二十五，可能是5的概率为百分之二十五，那么期望就是1 *50%+2 *25%+5 *25%
期望具有线性性，期望本来就是描述平均值的，所以一个随机变量的期望值也就是(x)=Ex
如果现在有个常量，因为他不会变，所有他的期望值为他自己，比如常量c的期望为c，那么既然如此E(x+c)显然应该为x的期望值加上c，因为无论如何c都是不变的，所以我们只需要考虑x的期望值就行了，也即可以把x+c当做一个整体，而c这一部分又是不动的，所以我们可以把它提出来，所以E(x+c)=Ex+c，如果是两个变量的和的期望呢？显然两个变量是独立的，而两个变量的和是不是应该等于他们两个变量自己的期望值相加呢？是的，所以E(x+y)=Ex+Ey，如果是乘法呢？显然如果一个变量乘一个常量的期望值应该可以把常量提出来，因为无论你变量为多少，都要乘这个常量，所以E(x*c)=cEx，当然最后还可以得出E(kx+c)其中k，c为常量，则E(kx+c)=kEx+c

全概率公式：

如果 Bn|n=1,2,3... 是一个概率空间的有限或者无限可数集，那么有全概率公式为

P(A)=∑i=1nP(A|Bi)P(Bi)

貌似很显然，概率为某B事件发生的概率乘以B事件发生了导致A事件发生的概率的求和

条件期望全期望公式：

pij=P(X=xi,Y=yi)

E(E(Y|X))=∑niP(X=xi)E(Y|X=xi)

=∑nipi∑kykpikpi

=∑ni∑kykpipikpi

=∑ni∑kykpik

=E(Y)

所以有 E(E(Y|X))=E(Y)=∑niP(X=xi)E(Y|X=xi)

标签：

相关文章