问题：
问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
解决方法：
动态规划
解题思路：
（理解一个前提，动态规划都是从最小开始逐步增加的）
第一步：设变量
先设i为印章数量，同时i <= m（m是输入的小A购买的印章数量）；设j为当前收集的图案数量，同时j <= n（n 为输入的印章图案个数）；设dp[i][j]为当有m张印章时，收集到j种图案的概率。（有点儿小饶，建议停下来，手写理解）
第二步：分情况分析概率（第三种情况开始用到动态规划来分析）
情况一：当输入的n（印章图案）只有一种的时候，那么收集n种图案的概率就会永远等于1（题目有说，购买印章的数量>0），即dp[i][j] = 1
情况二：当输入的n（印章图案）大于 m（小A购买的印章数量），此时需要收集的图案都没有购买的数量那么多，显然，集齐图案的概率为0，即dp[i][j] = 0
-
情况三：
（这里开始回到动态规划上，开始有些饶了，建议自己边看边手写手动分析）当j=1(当前收集的图案数量=1)，表示小A手里有i张印章且收集到了一种图案的概率，也就是说需要小A手里的这i张印章全部都是一个类型，此时概率dp[i][j] = n *(1/n)^i = (1/n)^(i-1) （建议自己从i = 0张开始分析)
接下来分析下当我们买了i张印章时要集齐j种是不是要分情况：
- 买到重复的时候
- 没有买到重复的时候
- 当买到重复的时候是不是意味着我还要抽到之前抽到过的某一种印章？
-
买到重复图案：
容易发现此时我已经有了j种图案，那么此时我购买到重复的概率是j/n；此时我在和买i-1张集齐j种的概率相乘才意味着我在买i张的时候集齐了j种图案的概率，即dp[i][j]=d[i-1][j] ***(j/n) -
没有买到重复图案：
即此时我买i-1张的时候有了j-1种印章，我要在买i张的时候买到不是重复的概率是(n-(j-1))/n，在与之前的概率进行相乘，才能意味着我在买i张的时候集齐了j种图案，即dp[i][j]=d[i-1][j-1] ***(n-(i-1)/n) -
最后：
把两者相加，便是买到第i张集齐第j种的概率，即dp[i][j]=d[i-1][j] *(j/n) + d[i-1][j-1] *(n-(i-1)/n)
实现代码：
java实现代码这儿还有点儿小技巧，因为需要用到i-1这种，然后在设置概率数组的时候就+1，即new double[m+1][n+1]，后面还有需要注意把Int转成double的，不然概率会得到0哦。
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
double[][] dp = new double[m+1][n+1];
if(n == 1) {
dp[m][n] = 1;
System.out.printf("%.4f", dp[m][n]);
return;
}
if(n > 1 && m < n) {
dp[m][n] = 0;
System.out.printf("%.4f", dp[m][n]);
return;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if (i < j) {
dp[i][j] = 0;
}
if (j == 1) {
dp[i][j] = Math.pow((1.0/n), (i-1));
} else {
dp[i][j] = dp[i-1][j] * (j*1.0 / n) + dp[i-1][j-1] * ((n - j +1)*1.0 / n);
}
}
}
System.out.printf("%.4f", dp[m][n]);
}
}
最后：
完结撒花，啦啦啦啦。（动态规划我也没咋学，这些也是参照各种资料倒腾出来的，有出错的地方，请大佬指出）
