POJ 2096 Collecting Bugs[数学期望]

　　为了理解期望DP做的第一道期望题。

　　一共有s个子系统和n个bug，一次能找一个Bug，求出在s个子系统中发现n个Bug的期望次数。bug是无穷的，所以认为每次在每个系统找找到一个Bug的概率是相等的。

　　这种题目基本都是设E(now)为从当前状态到达结束状态的期望，E(now)=∑E(x)p(x)，x表示可以从now转移到的状态，p[x]表示转移到这个状态的概率。

/*
s个子系统,n个bug,
e[i][j],在i个子系统中发现j个bug到达目标的期望,显然d[s][n]=0;
e[i][j]可以转化成四种情况
发现无用的bug             e[i][j]*(i/s)*(j/n)
在一个新系统中发现新bug   e[i+1][j+1]*(1-i/s)*(1-j)/n)
在一个新系统中发现旧bug   e[i+1][j]*(1-i/s)*(j/n)
在一个旧系统中发现新bug   e[i][j+1]*(i/s)*(1-j/n)
加起来 e[i][j]=e[i][j]*(i*j)/(s*n)+....+1
移项   e[i][j]=(...+1)/(1-(i*j)/(s*n))
最后d[0][0]即为所求
*/
#include <string.h>
#include <stdio.h>
double e[1005][1005],div;
int n,s;
int main(){
    while(scanf("%d%d",&n,&s)!=EOF){
        e[s][n]=0,div=n*s;
        for(int i=s;i>=0;i--){
            for(int j=n;j>=0;j--){
                if(i==s&&j==n)continue;
                e[i][j]=(((s-i)*(n-j)*e[i+1][j+1]+(s-i)*j*e[i+1][j]+(n-j)*i*e[i][j+1])/div+1)/(1-i*j/div);
            }
        }
        printf("%.4f\n",e[0][0]);
    }
    return 0;
}