Topic describes

If you throw n dice on the ground, the sum of all the dice that face up is s. Enter n and print out the probabilities for all possible values of S.

You need to return the answer with a floating-point array, where the ith element represents the probability of the ith smallest of the n dice that can be rolled.

Example 1: input: 1 output: [0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667]

Example 2: input, output: 2 [0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778]

Dynamic programmingK god ideas

  1. It is easy to know that when there is a die, each number has a 1/6 probability, so the initial dp is [1/6] * 6
  2. Starting with two dice, using forward recursion, shift and add all the values in dp, since the minimum of the two dice is 2 and the maximum is 12, i.e. (5 * num + 1)

Main DP ideas can refer to K god’s solution, here will not be wrong guidance

The sample code

def dicesProbability(self, n: int) - >List[float] :
    dp = [1 / 6] * 6

    for num in range(2, n + 1):
        temp = [0] * (5 * num + 1)
        for i in range(len(dp)):
            for j in range(6):
                temp[i + j] += dp[i] / 6
        dp = temp

    return dp
Copy the code