【剑指offer：n个骰子的点数】两种思路：递归+动态规划

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

// ac地址：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
// 原文地址：https://xxoo521.com/2020-03-29-two-sum/
/**
 * @param {number} n
 * @return {number[]}
 */
var twoSum = function(n) {
    const map = new Map();
    const totalTimes = Math.pow(6, n); // 出现的总次数
    inner(0, 1);

    const res = [];
    for (const times of map.values()) {
        res.push(times / totalTimes);
    }

    return res;

    /**
     * @param {number[]} total
     * @param {number} step
     */
    function inner(total, step) {
        if (step > n) {
            map.set(total, map.has(total) ? map.get(total) + 1 : 1);
            return;
        }

        for (let i = 1; i <= 6; ++i) {
            inner(total + i, step + 1);
        }
    }
};

// ac地址：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
// 原文地址：https://xxoo521.com/2020-03-29-two-sum/
/**
 * @param {number} n
 * @return {number[]}
 */
var twoSum = function(n) {
    const dp = new Array(n + 1);
    for (let i = 1; i <= n; ++i) {
        dp[i] = new Array(67).fill(0);
    }

    for (let j = 1; j <= 6; ++j) {
        dp[1][j] = 1;
    }

    // 骰子个数
    for (let i = 2; i <= n; ++i) {
        // i个骰子能够到达的最大值
        for (let j = i; j <= 6 * i; ++j) {
            // 状态转移
            for (let k = 1; j - k > 0 && k <= 6; ++k) {
                dp[i][j] += dp[i - 1][j - k];
            }
        }
    }

    let totalTimes = Math.pow(6, n);
    const ans = [];
    for (let j = n; j <= n * 6; ++j) {
        ans.push(dp[n][j] / totalTimes);
    }
    return ans;
};