题意：
一个软件有s个子系统，有很多个bug，公司boss要求他在每个子系统中至少找到一个bug即可，总共要找出n种个类型bug。
这个人每天能稳定找出一个bug，且属于任何一个子系统的概率是相等的（bug数量接近无穷大）出现在某个子系统的概率是1/s， 属于某种类型的概率是1/n，求完成这项工作所需期望天数。
思路：
设dp[i][j]表示在j个子系统中已经找到了i种类型bug，达到目标所需天数。所以dp[n][s]自然所需天数是0。每一天所找到的bug可以归类于下面4种类型：
1：dp[i][j] 表示发现了一个bug，但是与之前发现的bug属于同个类型，且在同一个子系统。
2：dp[i+1][j] 表示发现了一个bug，属于一个新的bug类型，虽然在同一个子系统。
3：dp[i][j+1] 表示发现了一个bug，虽然与之前发现的有重复，但是是在新的子系统发现。
4：dp[i+1][j+1] 表示发现了一个bug，属于一个新的bug类型，且在新的子系统里面发现。
那么公式可以写成：dp[i][j]=p1*dp[i][j]+p2*dp[i+1][j]+p3*dp[i][j+1]+dp[i+1][j+1]+1
两边变形下就变成：dp[i][j]=(1+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1])/(1-p1)
通过不断递推，最终能得出dp[0][0]的期望天数。
代码如下：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define p1 ((i*j) /m) #define p2 ((n-i)*j /m) #define p3 (i*(s-j) / m) #define p4 ((n-i)*(s-j) /m) double dp[1005][1005]; int main() { int n,s; memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&s); double m=n*s*1.0;//要特别留意这里，否则在做除法运算时会默认为int/int; 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]=(1+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1])/(1-p1); } printf("%.4f\n",dp[0][0]); return 0; }
