有买的印章数和印章种数两个变量,就自然而然地想成二维数组dp[i] [j]

关键是状态转移方程

这里参考https://blog.csdn.net/okok__TXF/article/details/121099645?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164758892616780357233576%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164758892616780357233576&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-121099645.142^v2^pc_search_result_control_group,143^v4^register&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AF%E5%8D%B0%E7%AB%A0&spm=1018.2226.3001.4187 的推导

设dp[i] [j]表示买 i 张凑齐 j 种印章的概率

难点是求出状态转移方程    初始条件可以很轻松的就知道

这里的状态转移方程如下

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

其实就是把  抽的第 i 张牌    考虑两种情况         
1.  抽到了之前抽到的牌
2.  抽到了新的牌



#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
 
int main(){
	double n,m;
	cin>>n>>m;
	int i,j;
	double dp[21][21]={0};
	for(i=0;i<m;i++) dp[i][0]=pow(1/n,double(i));
	for(i=1;i<n;i++) dp[0][i]=0;
	for(i=1;i<m;i++){
		for(j=1;j<n;j++) dp[i][j]=dp[i-1][j]*((j+1)*1/n)+dp[i-1][j-1]*(1-j/n);
                         //由于i与j为角标,所以带入推理出来的公式时i,j要+1
	}
	cout.setf(ios::fixed);
	/*
	for(i=0;i<m;i++){
		for(j=0;j<n;j++) cout<<fixed<<setprecision(4)<<dp[i][j]<<" ";
		cout<<endl;
	}
	*/
	cout<<fixed<<setprecision(4)<<dp[int(m-1)][int(n-1)]; //保留4位小数
}