【题意】

一个软件有 s 个子系统，存在 n 种 bug。某人一天能找到一个 bug。问，在这个软件中找齐 n 种 bug，并且每个子系统中至少包含一个 bug 的时间的期望值（单位：天）。注意：bug 是无限多的，每个 bug 属于任何一种 bug 的概率都是 1/n；出现在每个系统是等可能的，为 1/s。

【分析&解题思路】

令  dp[i][j] 表示已经找到了 i 种 bug，且 j 个子系统至少包含一个 bug，距离完成目标需要的时间的期望。

目标状态是 dp[0][0]


再过一天找到一个 bug 可能是如下的情况：

        1. 这个 bug 的种类是 已经找到的 并且 出现在 已经找到 bug 的子系统中

        2. 这个 bug 的种类是 已经找到的 并且 出现在 没有找到 bug 的子系统中

        3. 这个 bug 的种类是 没有找到的 并且 出现在 已经找到 bug 的子系统中

        4. 这个 bug 的种类是 没有找到的 并且 出现在 没有找到 bug 的子系统中

 

经过简单的分析，不难得出如下递推过程：

        dp[i][j] =    i/n*j/s*dp[i][j]

                     + i/n*(s-j)/s*dp[i][j+1]

                     + (n-i)/n*j/s*dp[i+1][j]

                     + (n-i)/n*(s-j)/s*dp[i+1][j+1]

 

移项可得

         (1-(i*j)/(n*s))dp[i][j] =    i/n*(s-j)/s*dp[i][j+1]

                                          + (n-i)/n*j/s*dp[i+1][j]

                                          + (n-i)/n*(s-j)/s*dp[i+1][j+1]

逆向递推即可

【参考blog】点击打开链接

[AC代码]

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
double dp[maxn][maxn];
int n,s;
int main(){
    while(~scanf("%d%d",&n,&s)){
        //memset(dp,0,sizeof(dp));
        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]=(i/n*(s-j)/s*dp[i][j+1]+(n-i)/n*j/s*dp[i+1][j]+(n-i)/n*(s-j)/s*dp[i+1][j+1])/(1-(i*j)/(n*s));
                double p1=(double(s-j)*i)/n/s;
                double p2=(double(n-i)*j)/n/s;
                double p3=(double(n-i)*(s-j))/n/s;
                double p0=(1.0-(double(i*j))/n/s);
                dp[i][j]=p1*dp[i][j+1]+p2*dp[i+1][j]+p3*dp[i+1][j+1]+1;//注意天数的期望，每一次相当于多了一天。
                dp[i][j]/=p0;
            }
        }
        printf("%.4f\n",dp[0][0]);
    }
    return 0;
}