蓝桥杯-算法训练 印章

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。

输入格式

一行两个正整数n和m

输出格式

一个实数P表示答案，保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

1≤n，m≤20

刚刚看到题目的时候，一开始以为是用高中学的概率论，组合数来做，但是后来发现自己实在是想不到，太复杂了，而且概率论也很久没学了，那么没办法了，只能是用动态规划来解决了

动态规划主要分为两步

首先，我们知道，如果挑出一张牌，想要只抽中一种牌的概率肯定为1，接着，我们往下继续分析

我们现在思考一下，如果挑出i张牌，最后只抽中1种牌的概率是多少？

第一次肯定是1，第二次还是得抽中这张牌，那么概率就是 1 n frac{1}{n} n1​,第三次还是这张牌，概率为 ( 1 n ) 2 (frac{1}{n})^2 (n1​)2，推算下来，我们想要i张牌全部抽中1种牌的概率就是 ( 1 n ) i − 1 (frac{1}{n})^{i-1} (n1​)i−1

至此，初始状态已经确定了

特殊的，当 i < j i 第二步：推算动态转移方程

这题动态转移方程有点难推理，但是也不是不能推理

当前我们要抽i张牌，并且要保证这i张牌中正好有j种牌，现在我们要对抽 i − 1 i-1 i−1张牌的状态进行分析

假设我们在抽第 i − 1 i-1 i−1张牌的时候，已经有j种牌了，那么此时，我们在抽第 i i i张牌时还要保证这i张牌正好有j种牌，那么我们这时候不得不抽中这j种牌中任何一张，所以概率是 d p [ i − 1 ] [ j ] ∗ j n dp[i-1][j]*frac{j}{n} dp[i−1][j]∗nj​假设我们在抽第 i − 1 i-1 i−1张牌是，手上只有 j − 1 j-1 j−1种牌，那么此时，我们要保证这 i i i张牌中正好有j种牌，我们只能从这 j − 1 j-1 j−1种牌外再抽出一张，概率为 d p [ i − 1 ] [ j − 1 ] ∗ n − j + 1 n dp[i-1][j-1] * frac{n-j+1}{n} dp[i−1][j−1]∗nn−j+1​

最后我们可以得出动态转移方程：
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ∗ j n + d p [ i − 1 ] [ j − 1 ] ∗ n − j + 1 n dp[i][j] = dp[i-1][j]*frac{j}{n}+dp[i-1][j-1]*frac{n-j+1}{n} dp[i][j]=dp[i−1][j]∗nj​+dp[i−1][j−1]∗nn−j+1​
至此，此题已经分析完毕，剩下按照基本方法推就行了

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //第一维界表示的是买彩票的张数，第二维界表示要凑齐的张数
        double[][] dp = new double[m+1][n+1];

        //买一张只凑齐1种的概率一定为1
        dp[1][1] = 1;

        //初始化
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){

                if(i