蓝桥杯--印章(DP动态规划)

蓝桥杯--印章(DP动态规划)

import java.util.Scanner;
public class BlueBridge_first_01_seal {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//n为总共的样式
int n = sc.nextInt();
//m为总共购买的次数
int m = sc.nextInt();
//防止数组越界
double[][] arr = new double[m+1][n+1];
//每一次购买的概率
double p = 1.0/n;
//i 次数 j 种类
for(int i =1;i<=m;i++) {
for(int j =1;j<=n;j++) {
if(i<j) {
arr[i][j]=0.0;
}else if(j==1) {
arr[i][j] = Math.pow(p, i-1);
}else {
//包括重复和不重复两种情况
//如果买到重复印章,如果买到重复印章,
//此时我有 j 种,
//那此时购买到重复印章的概率就是 j / n 。
//这时,我再和购买此重复印章前(购买i-1次时)的概率相乘,
//才可以表示我在买了i张印章时,集齐了j种,即arr[i][j] = arr[i-1][j]*(j/n);
/**2)如果没购买到重复印章,
* 此时我买了 i-1次,并且有 j-1 种,
* 那么此时购买非重复印章的概率就是 (n - (j-1))/ n。
* 这时,我再和购买此非重复印章前(购买i-1次时)的概率相乘,
* 才可以表示我在买了i张印章时,集齐了j种,
* 即arr [i][j] = arr[i-1][j-1]*((n-(j-1))/n);
*
*
*/
//arr[i][j] = arr[i-1][j] *(j/n)+arr[i-1][j-1]*((n-(j-1))/n);
arr[i][j]=arr[i-1][j]*(j*p)+arr[i-1][j-1]*((n-(j-1))*p);
}



}
}
System.out.printf("%.4f",arr[m][n]);
}

}

上一篇:第十四天155. 最小栈


下一篇:【Leetcode】 C语言 228. Summary Ranges