271. Dice Total Odds
A board-game night uses n fair six-sided dice, each face from 1 to 6 equally likely and all dice independent. All of them are rolled together and the faces are added up. Given the integer s, return the probability that the total is exactly s as a double. If s is impossible (smaller than n or larger than 6n) return 0.
Probabilities can be extremely small for large n, so enumerating outcomes is hopeless; count by total with dynamic programming over the dice. Answers within 1e-9 of the true value are accepted. Target O(n * 6n) time and O(6n) space.
Example 1
- Input:
- n = 3, s = 14
- Output:
- 0.06944444444444445
- Explanation:
Of the 216 equally likely outcomes of three dice, 15 sum to 14, giving 15/216.
Example 2
- Input:
- n = 5, s = 31
- Output:
- 0
- Explanation:
Five dice reach at most 30, so a total of 31 is impossible and the probability is 0.
Example 3
- Input:
- n = 2, s = 7
- Output:
- 0.16666666666666669
- Explanation:
Six of the 36 outcomes of two dice sum to 7, so the probability is 1/6.
Constraints
1 ≤ n ≤ 30
0 ≤ s ≤ 200
Absolute error up to 1e-9 is accepted.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-9: |answer - expected| <= 1.0E-9 x max(1, |expected|).
- Tolerance
1e-9
Expected complexity
- Time
- O(n^2)
- Space
- O(n)