题意：有s个系统，n种bug,一个程序员每天可以发现一个bug，求发现存在s个系统,n种bug的天数的期望
思路：定义dp[i][j]是已经发现i种bug,j个系统的期望
dp[i+1][j+1] 表示在一个新的系统中发现新bug 它的概率为 (n-i)/n*(s-j)/s
dp[i+1][j] 表示在一个已经发现过的系统中发现了一种新的bug 概率为 (n-i)/n*j/s
dp[i][j+1] 表示在一个新系统中发现一种已经发现过的bug 概率为 i/n*(s-j)/s
dp[i][j] 表示在一个已经发现过的系统中发现一种已经发现过的bug 概率为 i/n*j/s
根据期望的定义 E(aA+bB+cC+dD+...)=aEA+bEB+....;//a,b,c,d...表示概率,A,B,C...表示状态
dp[i][j]=p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i][j]+1
dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+1)/(1-p4)
代码：
#include <iostream> #include <cstdio> using namespace std; double dp[1005][1005]; int main() { int n,s; while(cin>>n>>s) { dp[n][s]=0; for(int i=n;i>=0;i--) { for(int j=s;j>=0;j--) { if(i==n&&j==s) continue; double p1=(n-i)*(s-j)/(n*s*1.0); double p2=(n-i)*j/(n*s*1.0); double p3=i*(s-j)/(n*s*1.0); double p4=(i*j)/(n*s*1.0); dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+1)/(1.0-p4); } } printf("%.4lf ",dp[0][0]); } return 0; }