吐槽
刷这些题让感觉我回到了高中时代，真的处处是公式！现在大三了，数学公式真的忘记七七八八了，忒难受的。平时在力扣刷题，力扣题目风格跟这些竞赛题目有很大的差别，多少有点接受不了，说句实在话，这些题跟我在力扣刷的那些中等题还要难些..但是没办法呀，谁叫我想去北京呢？只能一步一脚印了！推荐大家一个刷题网站AcWing，里面的东西，真的good！
题目
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
分析
这是一道动态规划的问题。根据题意“小A买了m张印章，求小A集齐n种印章的概率。”我们就要想到使用二维数组。
二维数组功能多多，能够记录买了多少张印章，集齐了多少种印章，以及出现这种情况的概率。比如小A买了3张印章，集齐2种印章的概率为0.75，用个二维数组（dp）就可以这么表示：dp[3][2] = 0.75。求买了m张印章，集齐n种印章的概率为dp[m][n]，我们只要求出dp[m][n]就能得出正确答案。
dp[m][n] 表示买了m张印章，集齐n种印章的概率。而选取每个印章的概率P就是1/n。
分类讨论
很显然，我们不能马上得出结果，必须要先进行分类讨论。
1. 集齐数大于购买数
要集齐的种类还大于购买的数量那样是不可能集齐的。转化成计算机语言就是
if j > i: dp[i][j] = 0讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/124017.html