This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The number of n dice

Answer key

Method 1: Dynamic programming – Java

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.

Let’s say I have the solution f(n-1) for n-1 dice, and I add a die, and I find the probability f(n, x) that the sum of n dice is x.

When the number of dice added is 1, the sum of the first n-1N −1 dice should be X-1 to form the number and X. Similarly, when this die is 22, the first n-1 die should be X-2; And so on, until the die is 6. If you add up the probabilities of these six things, you get the probability f(n, x). The recursion formula is as follows:

F (n,x) = I =1∑6 f(n−1,x− I) × 1/6

The usual approach is to declare a two-dimensional array dp, where dp[I][j] represents the number of the first I dice and the probability of j, and perform a state transition. As DP [I] is only derived from DP [i-1] recursively, in order to reduce space complexity, only two one-dimensional arrays dp are established, and TMP can advance alternately.

class Solution {
    public double[] dicesProbability(int n) {
        if (n <= 0) {
            return new double[0];
        }

        double[] dp = new double[70];
        // Initialize the first die
        for (int i = 1; i <= 6; i++) {
            dp[i] = 1;
        }

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

Time complexity: O (n^2)

Space complexity: O (n)

Method 1: Dynamic programming — Go

func dicesProbability(n int) []float64 {
	dp := make([] []float64, n)
	for i := range dp{
		dp[i] = make([]float64, (i + 1) * 6 - i)
	}
	for i := range dp[0]{
		dp[0][i] = float64(1) / float64(6)}for i := 1; i < len(dp); i ++{
		for j := range dp[i - 1] {for k := range dp[0]{
				dp[i][j + k] += float64(dp[i - 1][j]) * float64(dp[0][k])
			}
		}
	}
	return dp[n - 1]}Copy the code