1.題目

2.代碼

#共有n種圖案的印章，每種圖案的出現概率相同。小A買了m張印章，求小A集齊n種印章的概率。
n,m=map(int,input().split())
dp=[[0 for i in range(n+1)]for j in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if(j>i):
            dp[i][j]=0
        elif(j==1):
            dp[i][j]=pow(1/n,i-1)
        else:
            dp[i][j]=(dp[i-1][j])*(j*1.0/n)+(dp[i-1][j-1])*((n-j+1)*1.0/n)
print('{:.4f}'.format(dp[m][n]))

3.代碼解析

這個題我開始想的第一個方法是深搜，因為想著每一個都是選擇的問題，沒一次的選項都一樣，但是發現如果每一次搜索的很多的話很費時間，而且去寫代碼的時候思路也不是很清晰。

后面按照藍橋杯的提示說是dp（動規），因此換了方法。

首先按照輸入n,m,這里是python藍橋杯中常用的輸入方法:

map(int,input().spilt)

這里的map就是映射，將input().spilt切割后的數都用int函數轉換為int型。

?*重點（別把上面的i和j和下面的i和j看反了）：dp數組就是在初始已知的值中去考慮遞進的狀態

（1）j>i的情況，即當只買了i張，集贊到對應j張的概率，這是不可能的，因為為0。進行以下初始化

if(j>i):
    dp[i][j]=0

（2）j=1:的情況，即集贊到j的概率，這種情況下，一張就是需要的那張那個就概率為1/n

（3）其他情況，對于買了i張集贊到對應j張的概率=買了i-1張積攢 j 張的概率*（新的一次再一次選中j張中的一張的概率）+買了i-1張積攢 j-1 張的概率*（選中n張目標圖中除去不在目標圖j數目中的概率）

dp[i][j]=(dp[i-1][j])*(j*1.0/n)+(dp[i-1][j-1])*((n-j+1)*1.0/n)