【印章】DP问题（Python）

共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式：一行两个正整数n和m
输出格式：一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500

数据规模和约定：1≤n，m≤20

由于Python中没有数组的数据类型，借助二维列表进行实现

# 总共n种，买了m张，集齐n种的概率
n , m = map(int,input().split())


dp = [[0 for i in range(n + 1)] for i in range(m + 1)] 

"""
当n = 2，m = 3时，
dp 的样子
[
  [ 0 0 0 ]
  [ 0 0 0 ]
  [ 0 0 0 ]
  [ 0 0 0 ]
]

"""

# dp[i][j] 表示买了i张，凑齐了j种
for i in range(1 , m + 1):
    for j in range(1 , n + 1):
        if i < j :
            dp[i][j] = 0
        elif j == 1:
            dp[i][j] = pow(1 / n ,i - 1)
        else:
            dp[i][j] = dp[i-1][j] * (1/n) * j + dp[i-1][j-1] * (1/n)*(n-(j-1))

print("{:.4f}".format(dp[m][n]))