【转】dp求期望的题。题意：一个软件有s个子系统，会产生$n$种$bug$。

某人一天发现一个$bug$，这个$bug$属于某种$bug$，发生在某个子系统中。

求找到所有的$n$种$bug$，且每个子系统都找到$bug$，这样所要的天数的期望。

 

需要注意的是：$bug$的数量是无穷大的，所以发现一个$bug$，出现在某个子系统的概率是$1/s$，属于某种类型的概率是$1/n$。

 

解法：$dp[i][j]$表示已经找到$i$种$bug$，并存在于$j$个子系统中，要达到目标状态的天数的期望。

显然，$dp[n][s]=0$，因为已经达到目标了。而$dp[0][0]$就是我们要求的答案。$dp[i][j]$状态可以转化成以下四种：

　　$dp[i][j]$　　　　发现一个$bug$属于已经找到的$i$种$bug$和$j$个子系统中

　　$dp[i+1][j]$　　　　发现一个$bug$属于新的一种$bug$，但属于已经找到的$j$种子系统

　　$dp[i][j+1]$　　　　发现一个$bug$属于已经找到的$i$种$bug$，但属于新的子系统

　　$dp[i+1][j+1]$　　　　发现一个$bug$属于新的一种$bug$和新的一个子系统

 

以上四种的概率分别为：

　　$p1={i*j}/{n*s}$;

　　$p2={n-i}*j/{n*s}$;

　　$p3={i*(s-j)}/{n*s}$;

　　$p4={(n-i)*(s-j)}/{n*s}$

 

又有：期望可以分解成多个子期望的加权和，权为子期望发生的概率，即

　　$E(aA+bB+...) = aE(A) + bE(B) +...$

所以：

　　${dp[i,j]=p1*dp[i,j]+p2*dp[i+1,j]+p3*dp[i,j+1]+p4*dp[i+1,j+1]+1}$;

整理得：

　　${dp[i,j]=\frac{1+p2*dp[i+1,j]+p3*dp[i,j+1]+p4*dp[i+1,j+1]}{1-p1 }}$

 

　　${=\frac{n*s+(n-i)*j*dp[i+1,j]+i*(s-j)*dp[i,j+1]+(n-i)*(s-j)*dp[i+1,j+1]}{n*s-i*j}}$

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 9 using namespace std;10 11 double m,f[1100][1100];12 13 int main()14 {15 int n,s,i,j;16 17 scanf("%d%d",&n,&s);18 m=n*s;19 f[n][s]=0.0;20 for(i=n;i>=0;--i)21 {22 for(j=s;j>=0;--j)23 {24 if(i==n && j==s)continue;25 f[i][j]=(m+(n-i)*j*f[i+1][j]+i*(s-j)*f[i][j+1]+(n-i)*(s-j)*f[i+1][j+1])/(m-i*j);26 }27 }28 printf("%.4f\n",f[0][0]);29 return 0;30 }