1、试题 算法训练 印章 dp题(动态规划题)
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
思路：dp题一般使用数组寻找规律，一维数组，二维数组都很常见，甚至是三维n维
此题建议使用二维数组
1、当m
2、当n>1，m>n时，开始寻找规律
建立数组dp[m+1][n+1]因为要使用到d[m][n]所以进行+1操作
当我们买了i张印章时集齐1种的概率是不是(1/n)^(i-1)（此时n种印章）
当我们买了i张印章时要集齐j种是不是要分情况？
1、买到重复的时候
2、没有买到重复的时候？
当买到重复的时候是不是意味着我还要抽到之前抽到过的某一种印章？
此时我已经有了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种
把两者相加，便是买到第i张集齐第j种的概率
即d[i][j]可以算出来，那么当i=m,j=n时是不是也可以算出来？
下面上代码：
import java.util.Scanner;
public class YinZ {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int m=s.nextInt();
double p=1.0/n;
double[][] b=new double[m+1][n+1];
if (n==1){ //当n=1时m>n几率为1
b[m][n]=1;
System.out.printf("%.4f",b[m][n]);
return;
}
if (n>1&&m
System.out.printf("%.4f",b[m][n]);
return;
}
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n; j++) {
if (i
b[i][j]=Math.pow(p,i-1); //当i张集齐1种的概率
}else {
b[i][j]=b[i-1][j]*(j*1.0/n)+b[i-1][j-1]*((n-j+1)*1.0/n); //当i张集齐j种的概率
}
}
}
System.out.printf("%.4f",b[m][n]);
}
}
可能会有不足，望指正！
