Offer – n dice count (JS implementation)

Topic describes

Their thinking

• The problem can be solved by recursion or dynamic programming
• The idea is to understand the problem, to find the relationship between the number of dice and the sum of these dice

Core formula (this is hard to explain, the key is to understand the code)

$The total number of outcomes for n dice is equal to (this die is 1-6) + (n-1) is the sum of all outcomes for (and – (1-6))$

The problem solving code

var dicesProbability = function (n) {
    // The sum of n dice is [n,6n]
    // Return the final result array with a denominator of 6 to the n
    const total = Math.pow(6, n);
    const result = [];
    // Create a hash table to store the sum of the objects on the NTH die
    const m = new Map(a);for (let i = n; i <= 6 * n; i++) {
        // The following s refers to
        const denominator = helper(i, n);
        // Add each result separately to the final result
        result.push(denominator / total);
    }

    function helper(count, n) {
        // First check if the hash table has records of n-1 dice target sum
        let key = ` and:${count}- Number of dice:${n}`;
        if (m.has(key)) {
            return m.get(key);
        }

        if (count < n || count > 6*n) {
            return 0;
        }
        if (n === 1) {
            return 1;
        }
        let res = 0;
        The number of possible values of the specified sum is the sum of the target dice number -1, the current sum minus all the possibilities from 1 to 6
        for (let i = 1; i <= 6; i++) {
            res = res + helper(count - i,n-1,m);
        }
        m.set(key,res);
        return res;
    }
    return result;
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

• Lesson 1: Learn to solve recursively
• Revelation 2: Accurately understand the number of dice and the previous number of dice and the relationship between and, is the key to solve the problem
• Lesson 3: Learn to use hash tables