Offer 60. N dice roll

This is the 9th day of my participation in the August More Text Challenge

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: 2 output: [0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778]

Limitations:

1 <= n <= 11

Their thinking

The probability of a roll = the sum of the cases that make up the point/the number of cases

So the number of cases is equal to 6 to the n.

So we just need to count the number of times each roll occurs to figure out the probability of rolling that roll

To define an array

Dp [I][j] represents the number of cases in which I dice are used to produce a roll of J

Initialize the

A die can produce only one to six rolls, and each roll has a probability of one

        dp[1][1]=1;
        dp[1][2]=1;
        dp[1][3]=1;
        dp[1][4]=1;
        dp[1][5]=1;
        dp[1][6]=1;
Copy the code

State transition

Dp [I][j] is derived from the case of the i-1 die, and is derived from dp[i-1][j-k] (k is the number of possible rolls on the i-1 die) because the number of possible rolls on the i-1 die is 1 to 6.

for (int k=1; k<=6; k++) if(j-k>=0) dp[i][j]+=dp[i-1][j-k];Copy the code

code

class Solution {
    public double[] dicesProbability(int n) {


        int[][] dp = new int[n + 1] [6 * n + 1];
        dp[1] [1] =1;
        dp[1] [2] =1;
        dp[1] [3] =1;
        dp[1] [4] =1;
        dp[1] [5] =1;
        dp[1] [6] =1;

        int cnt=0;
        for (int i=2; i<=n; i++) {for (intj=i; j<=6*i; j++) {for (int k=1; k<=6; k++)if(j-k>=0)
                        dp[i][j]+=dp[i-1][j-k]; }}double v = Math.pow(6 , n);
        double[] res = new double[5 * n + 1];
        for (int i=n,j=0; i<=6*n; i++,j++) { res[j]=dp[n][i]/v; }returnres; }}Copy the code

Offer 60. N dice roll