leetcode 剑指 Offer 60. n个骰子的点数

 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;k7);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 };