題意：某人喜歡收集 Bug ，現給定 n 個 Bug 和 s 個程式 ，求在 s 個程式中找全 n 個 Bug 并且每一個程式都至少找到
一個 Bug 的機率
分析：設 dp[ i ][ j ] 表示找到了i 種 Bug ，并且 j 個程式都至少找到一個 Bug 的機率，則 dp[ i ][ j ]的組成有以下四種情況：
① dp[ i ][ j ] *
*
//找到的 Bug 屬于已經找到的 i 種 Bug 之一，并且出現在 j 個程式之中
② dp[ i+1 ][ j ] * ( 1 -
) *
//找到的 Bug 不屬于已經找到的 i 種 Bug ，并且出現在 j 個程式之中
③ dp[ i ][ j+1 ] *
* ( 1 -
) //找到的 Bug 屬于已經找到的 i 種 Bug 之一，但在 j 個程式之中沒有出現
④ dp[ i+1 ][ j+1 ] * ( 1 -
) * ( 1 -
) //找到的 Bug 不屬于已經找到的 i 種 Bug ，且在 j 個程式之中沒有出現
綜合以上四種情況，可以推出轉移方程：
dp[ i ][ j ] = dp[ i ][ j ] *
*
+ dp[ i+1 ][ j ] * ( 1 -
) *
+ dp[ i ][ j+1 ] *
* ( 1 -
)
+ dp[ i+1 ][ j+1 ] * ( 1 -
) * ( 1 -
)
移項可得 :
dp[ i ][ j ] = （ dp[ i+1 ][ j ] * ( 1 -
) *
+ dp[ i ][ j+1 ] *
* ( 1 -
) + dp[ i+1 ][ j+1 ] * ( 1 -
) * ( 1 -
) ）
/ （1 -
*
）
= （ dp[ i+1 ][ j ] * ( n - i ) * j + dp[ i ][ j+1 ] * i * ( s - j ) + dp[ i+1 ][ j+1 ] * ( n - i ) * ( s - j ) ）
/ （ n*s - i*j ）
代碼：
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1005;
double dp[N][N];
int n,s;
int main()
{
scanf("%d%d",&n,&s);
dp[n][s]=0;
double a,b,c,d;
for(int i=n;i>=0;i--)
for(int j=s;j>=0;j--)
{
if(i==n&&j==s) continue;
a = (double) (n-i)*j;
b = (double) i*(s-j);
c = (double) (n-i)*(s-j);
d = (double) n*s-i*j;
dp[i][j]=(dp[i+1][j]*a+dp[i][j+1]*b+dp[i+1][j+1]*c+n*s)/d;
}
printf("%.4f\n",dp[0][0]);
return 0;
}