试题 算法训练 印章-蓝桥杯

/*
	DP: Dynamic programming, 动态规划 。
	建议大家先在网上搜一搜动态规划 ，加深一下理解。 
	核心：拆分子，记住过往，减少重复计算，并用于计算结果。神似递归。	 
									2022/1/27  fevergo 明鹊 。。。 
	希望对你有帮助 。
*/
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int n, m;
	cin>>n>>m; 
	double pn = 1.0/n;
	
	double p[21][21]; 

	for(int i = 1;i<=n;i++) 
	for(int j = 1;j<=m;j++)
	{
		if(i>j) {p[i][j] = 0;}  
		if(i == 1) {p[i][j] = pow(pn, j-1);}
		else{p[i][j] = p[i][j-1]*(i*pn)+p[i-1][j-1]*((n-(i-1))*pn);} 
	}
		 
	printf("%.4lf", p[n][m]);
	
	return 0;
}

/*
	DP: Dynamic programming, 动态规划 。
	建议大家先在网上搜一搜动态规划 ，加深一下理解。 
	核心：拆分子，记住过往，减少重复计算，并用于计算结果。神似递归。	 
									2022/1/27  fevergo 明鹊 。。。 
	希望对你有帮助 。
*/
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int n, m;
	cin>>n>>m; // 有 n种印章， 买了 m个 
	double pn = 1.0/n; // 从印章里取一个的概率。 
	
	double p[21][21]; 
	// 初始化数组，记住过往。
	// p[i][j] 代表 现有 i 种,买 j个集齐的概率 （拆分子） 
	for(int i = 1;i<=n;i++) 
	for(int j = 1;j<=m;j++)
	{
		if(i>j) {p[i][j] = 0;} // 例如 现有 i种，买了j个，i>j, 肯定集不齐。 
		if(i == 1) {p[i][j] = pow(pn, j-1);}
		// 现有 1种，买了m个集齐 = 买了m个全是1种。
		else{p[i][j] = p[i][j-1]*(i*pn)+p[i-1][j-1]*((n-(i-1))*pn);} 
		// 现有 i 种，买了 j 个集齐 : 
		// 记住过往，减少重复计算，并用于计算结果，
        //1.重复的情况： p[i][j-1] * (i*pn) ，(i*pn)是最后一张重复的概率
		//2.不重复的情况： p[i-1][j-1]*((n-(i-1))*pn)， (n-(i-1))*pn是最后一张不重复的概率
	}
		 
	printf("%.4lf", p[n][m]); // 格式输出
	
	return 0;
}