蓝桥杯算法训练-Python实现

ALGO-1007 印章

“蓝桥杯”练习系统 (lanqiao.cn)

资源限制

​ 内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

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

输入格式

　　一行两个正整数n和m

输出格式

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

样例输入

​ 2 3

样例输出

​ 0.7500

数据规模和约定

​ 1≤n，m≤20

+++

此题采用动态规划（Dynamic Programming，DP）的方法求解，动态规划的三要素：最优子结构、边界和状态转移函数。

边界 问题最小子子集的解（初始范围）
最优子结构 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
状态转移函数 从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)
对于本题，