“This is the 20th day of my participation in the August Gwen Challenge.

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]Copy the code

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]Copy the code

Limitations:

  • 1 <= n <= 11

Answer key

Method 1: dynamic programming

The article may not be very clear about some of the details of the code, but most of these details can be found in the comments, and I have explained them in detail in the hope that they will be helpful.

Their thinking

The problem requires us to work out the probability of the occurrence of all points. According to the calculation formula of the occurrence probability of point K, the calculation formula of the occurrence probability of point K is:

P(k)= number of occurrences of k divided by total number of occurrences

If YOU roll n dice, the total number of times you can roll all the dice is 6 to the n, because there are n dice, and each of these dice has 6 possible outcomes. Our goal is to figure out how many times each roll occurs when we roll n dice.

The use of recursion creates double-counting problems

The time complexity of using recursive search solution space alone is 6^n, resulting in timeout errors because of repeated substructures. The explanation is as follows:

We use the recursive function getCount(n, k) to represent the number of times k occurs when n dice are rolled.

To simplify our analysis, let’s take the example of rolling 2 dice.

Let’s simulate counting the number of points 4 and 6, respectively. So you compute getCOunt of 2,4 and getCOunt of 2,6.

Their calculation formula is:

GetCount (2,4) = getCount(1,1) + getCount(1,2) + getCount(1,3) + getCount(2,6) = getCount(1,1) + getCount(1,2) + getCount(1,2) + GetCount (1,3) + getCount(1,4) + getCount(1,5)

GetCount (1,1) + getCount(1,2) + getCount(1,3)

For these substructures, there is also a lot of double counting when counting the number of other points.

Dynamic programming

Using dynamic programming to solve problems generally consists of three steps:

  1. According to state
  2. Find the state transition equation
  3. Boundary processing

Below we step by step analysis, I believe you will have harvest!

According to state

When analyzing the state of a problem, don’t analyze the whole, just the last stage! Because dynamic programming problems are divided into multiple stages, the state representation of each stage is the same, and our final answer is in the last stage.

So what’s the last stage of this problem?

We know from the problem that there are n dice rolled, so the last stage is obviously the number of times each roll occurs after n dice are rolled.

Note: The roll here refers to the sum of the first n dice, not the NTH die, as follows.

Finding the last stage, the state representation is easy.

  • The stages are represented in terms of the first dimension of the array, which is how many dice have been rolled.
  • And then we’re going to use the second dimension to represent the number of possible rolls after we roll these dice.
  • The value of the array represents the number of points in that phase.

So the state representation is dp[I][j], which is the number of times you roll j after you roll I dice.

Find the state transition equation

To find the transition equation is to find the transition relationship between the stages, and again we just need to look at the last stage, and look at how the state is done.

And then the final phase, the phase after n dice are rolled, we’ll call dp[n][j] the number of times the final phase j occurs.

Just looking at the NTH die, it might have a roll of 1, 2, 3, 4, 5, 6, because the number of j-1, J-2, J-3, J4, J5, and J6 after n dice are rolled can be translated from the number of j-1, J-2, J-3, J4, J5, and J6 after n dice are rolled.

For (die NTH I = 1; i <= 6; i ++) { dp[n][j] += dp[n-1][j - i] }Copy the code

The mathematical formula looks like this:

6 DP [n][J]= ∑ DP [N −1][j− I] I =1Copy the code

N is the phase, j is the sum of the number of rolls on n dice, and I is the six rolls on the NTH die.

Boundary processing

The boundary handling here is simple, as long as we initialize the state that we know directly.

The state we can directly direct is the state of the first stage: after rolling a die, its possible rolls are 1, 2, 3, 4, 5, 6, and each roll occurs 1 times.

for (int i = 1; i <= 6; i ++) {
    dp[1][i] = 1;
}
Copy the code

code

class Solution {
public:
   vector<double> twoSum(int n) {
       int dp[15][70];
       memset(dp, 0, sizeof(dp));
       for (int i = 1; i <= 6; i ++) {
           dp[1][i] = 1;
       }
       for (int i = 2; i <= n; i ++) {
           for (int j = i; j <= 6*i; j ++) {
               for (int cur = 1; cur <= 6; cur ++) {
                   if (j - cur <= 0) {
                       break;
                   }
                   dp[i][j] += dp[i-1][j-cur];
               }
           }
       }
       int all = pow(6, n);
       vector<double> ret;
       for (int i = n; i <= 6 * n; i ++) {
           ret.push_back(dp[n][i] * 1.0 / all);
       }
       return ret;
   }
}; 
Copy the code

Space optimization

We know that the state of each stage is only optimized with the state of the previous stage, so we don’t need an extra dimension to preserve all the stages.

A one-dimensional array is used to save the state of a stage, and then the point J that may appear in the next stage is traversed from large to small to achieve a stage by stage conversion.

The optimized code is as follows:

class Solution {
public:
    vector<double> twoSum(int n) {
        int dp[70];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= 6; i ++) {
            dp[i] = 1;
        }
        for (int i = 2; i <= n; i ++) {
            for (int j = 6*i; j >= i; j --) {
                dp[j] = 0;
                for (int cur = 1; cur <= 6; cur ++) {
                    if (j - cur < i-1) {
                        break;
                    }
                    dp[j] += dp[j-cur];
                }
            }
        }
        int all = pow(6, n);
        vector<double> ret;
        for (int i = n; i <= 6 * n; i ++) {
            ret.push_back(dp[i] * 1.0 / all);
        }
        return ret;
    }
};
Copy the code

Personal understanding

  1. Any problem that feels recursive can be realized by dynamic programming.
  2. To use dynamic programming, you have to implement the three steps of dynamic programming: states, state transition equations, and boundary values.
  3. Once we’ve identified the three steps above, we’ve actually solved the problem.
  4. The start of each array loop and the size of the array must be clear.

Attached is a Java version of the code I wrote

class Solution { public double[] twoSum(int n) { double[] result = new double[5*n+1]; int total = (int) Math.pow(6,n); int[][] dp = new int[n+1][6*n+1]; for (int i = 1 ; i <= 6; i++) { dp[1][i] = 1; } for (int i = 2; i <= n; i++) { for (int j = i; j <= 6*i; j++) { for (int current = 1; current <= 6; current ++) { if (j <= current) { break; } dp[i][j] += dp[i-1][j-current]; } } } for (int i = n; i <= 6*n; i++) { result[i-n] = (double) dp[n][i] / total; } return result; }}Copy the code

Answer key source

By Huwt Link: leetcode-cn.com/problems/ng… Source: LeetCode

source

Source: LeetCode link: leetcode-cn.com/problems/ng…