题目：
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
解题代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Seal { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; double[][] p = new double[m + 1][n + 1]; System.out.printf("%.4f", probability(p, n, m)); } public static double probability(double[][] p, int n, int m) { double x = 1.0 / n; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (i < j) { p[i][j] = 0.0; } if (j == 1){ p[i][j] = Math.pow(x, i-1); } else{ p[i][j] = p[i-1][j] * (j*x) + p[i-1][j-1] * ((n-j+1)*x); } } } return p[m][n]; } }
解题思路：
这里是怕我忘记，所以需要记忆一下
后面的概率需要前面的概率支持，就使用动态规划（DP）,一般来说都是使用二维数组解题。
又因为本题有两个参数，所以可以猜测使用二维数组dp[i][p]来表示 买 i 个其中有 j 种不同的概率。
分类讨论：
- i < j 时 ：
概率为0- j = 1 时：
- i = 1 时 为1，
因为买一种有一种的概率为 1
- i > 1 时 (1/n)^(i - 1)
意思是买 i 张但只有一种所以有 （1/n）^i
但是还要这种可能是n种种的任意一种，所以还要乘以 n- i > j 时：
买了 i 张得到了 j 种不同的情况，为两种情况相加，
即 买了 i - 1 张 得到了 j 种，即再买一张还是 j 种的 dp[i] [j] = dp[i-1] [j] * ( j / n )
和 买了 i - 1 张 得到了 j - 1 种，即再买一张是第 j 种的 dp[i] [j] = dp[i-1] [j-1] * (n-j+1) / n
