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

题目描述:把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例

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

解法 1:递归穷举所有情况(TLE)

这题可以使用递归来穷举所有情况。过程中,借助哈希表来存放每种情况对应的数值出现的次数。

// 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);
        }
    }
};

这种方法由于递归会有重复计算的问题,时间复杂度高达$O(6^n)$。

题目要求 n 的大小范围是[1, 11],当 n=11 的时候,会 TLE。

解法 2: 动态规划

dp 数组的含义:dp[i][j] 代表 i 枚骰子朝上一面之和到达 j 的总个数。

状态转移方程是:dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + dp[i-1][j-4] + dp[i-1][j-5] + dp[i-1][j-6]

代码实现如下:

// 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;
};

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×