[数据结构与算法]蓝桥杯 算法训练 印章

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#define ll long long
using namespace std;

int main(){
   int m,n;
   cin>>n>>m;
   double dp[m+1][n+1];
   double p=1.0/n;
  for(int i=1;i<=m;i++)
  {
      for(int j=1;j<=n;j++)
      {  
          if(i<j)dp[i][j]=0;//i<j不可能集齐
           if(j==1)dp[i][j]=pow(p,i-1);//base case
          else  dp[i][j]=dp[i-1][j]*(j*1.0/n)+dp[i-1][j-1]*((n-j+1)*1.0/n); //递推，由下至上 
      }
  }
   printf("%.4f",dp[m][n]);

    return 0;
}   //经典动态规划解法