1 class Solution { 2 public: 3 vector<double> dicesProbability(int n) { 4 int dp[n+1][70]; 5 memset(dp,0,sizeof(dp)); 6 for(int i=1;i<=6;i++)dp[1][i]=1; 7 for(int i=2;i<=n;i++) 8 for(int j=i;j<=i*6;j++) 9 for(int k=1;k<min(j,7);k++) 10 dp[i][j]+=dp[i-1][j-k]; 11 12 vector<double>ans; 13 long long cnt=0; 14 for(int i=1;i<=6*n;i++)cnt+=dp[n][i]; 15 for(int i=n;i<=6*n;i++)ans.push_back(1.0*dp[n][i]/cnt); 16 return ans; 17 /* 18 暴力dfs会T, o(6^n) 19 dp[i][j]表示前i个骰子和为j的数目; 20 dp[i][j]=dp[i-1][j-k] (k [1--6]) 21 */ 22 } 23 };