60. n个骰子的点数
1. 描述
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
2. 例子
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
3. 限制
- 1 <= n <= 11
4. 题解
时间复杂度: O($MaxPoint^2n^2$)
空间复杂度: O($MaxPoint^n$)
动态规划
dp[i][j] 意味着第 i 个色子中所有点数和为 j 的情况数量
$ dp[i][j] = \begin{cases} 1, & \text{i == 1} \\
\sum_{i = 1}^{MaxPoint} {dp[i-1][j-i]} , & \text{i > 1} \\
\end{cases} $
class Solution
{
private:
const int MaxPoint = 6;
public:
vector<double> dicesProbability(int n)
{
vector<int> lastRoundPoints(MaxPoint * n + 1), currentRoundPoints(MaxPoint * n + 1);
for(int i = 1; i <= MaxPoint; i++)
lastRoundPoints[i] = 1;
for(int round = 2; round <= n; round++)
{
for(int point = round; point <= round * MaxPoint; point++)
{
int sum = 0;
for(int i = max(point - MaxPoint, round - 1); i < point && i <= MaxPoint * (round - 1); i++)
sum += lastRoundPoints[i];
currentRoundPoints[point] = sum;
}
swap(lastRoundPoints, currentRoundPoints);
}
int valueCount = pow(MaxPoint, n);
vector<double> probability((MaxPoint - 1) * n + 1);
for(int i = n, j = 0; i <= MaxPoint * n; i++, j++)
probability[j] = (double)lastRoundPoints[i] / valueCount;
return probability;
}
};