剑指Offer题解 - Day66

剑指 Offer 60. n 个骰子的点数

力扣题目链接[1]

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

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

「示例 1:」

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

「限制：」

1 <= n <= 11

分析：

首先考虑使用暴力法。先根据题目描述总结以下结论：

• 每个骰子摇到1~6的概率相等，均等于1/6；
• 一个骰子的点数之和有6种情况，两个骰子的点数之和有36种情况，n个骰子有6^n 种情况。
• n个骰子的点数之和范围是[n, 6n] ，点数出现的可能性个数是 6n - n + 1 = 5n + 1。

如果使用暴力法，需要统计每个点数和的出现次数，然后除以点数之和的总数6^n 。由题目可知，1 <= n <= 11 ，因此暴力法是无法接受的。

动态规划

此题可以通过动态规划求解。因此我们需要找出dp方程。核心的问题在于，假设n - 1个骰子的解是f(n - 1)，如何递推出n个骰子的解f(n) 。

• 假设n个骰子点数之和为x的解为f(n, x) ；
• 如果当前添加的骰子点数是1，那么n - 1个骰子的点数之和就是x - 1。以此类推直到当前添加的骰子点数是6，那么n - 1个骰子的点数之和就是x - 6。由此可得：f(n - 1, x - i)的累加和除以6就是f(n, x)的解。其中，i的取值范围是1~6。
• 而f(1)的解是已知的，因此可以通过上述方程求出f(n)。

由此，我们得出了逆向求解方程。此时衍生出一个新的问题，x可能会越界。如果x小于6的话，此时的计算是毫无意义的。

那么可以换一种思维，先求出f(n - 1)中各点数和的概率。而f(n - 1, x)仅与f(n, x + i)相关，其中i的取值范围是1~6。这样就可以完成f(n - 1)到f(n) 的递推。

/**
 * @param {number} n
 * @return {number[]}
 */
var dicesProbability = function(n) {
    let dp = Array(6).fill(1 / 6); // 初始化一个骰子的点数之和概率
    for (let i = 2; i <= n; i++) { // 处理2-n个骰子的点数之和
        let temp = Array(5 * i + 1).fill(0); // 初始化点数之和出现情况
        for (let j = 0; j < dp.length; j++) { // 上一轮骰子的概率
            for (let k = j; k < j + 6; k++) { // 本轮骰子的投掷情况
                temp[k] += dp[j] / 6; // 重点，下面分析
            }
        }
        dp = temp; // 赋值给dp，方便下一次循环
    }
    return dp;
};

• 时间复杂度 O(n^2)。
• 空间复杂度 O(n)。

分析：

首先初始化f(1) 的结果。然后开始求f(2)，直到f(n) 。在外层循环内部，首先初始化n个骰子点数之和出现的可能性。然后在中层循环中根据上一轮概率来求解。

根据刚才得出的结论，f(n - 1, x) 仅与f(n, x + i) 相关，所以内层循环的起始值，与中层循环的j有关。而且k只需要累加6次。

内层循环里的表达式代表着：当添加本轮骰子时，骰子点数之和为k的值等于原有的值加上本轮投出1-6中某个点数的概率。而本轮投出1-6中某个点数的概率等于上一轮概率除以6。

每添加一个骰子，就将结果赋值给dp，方便进行下一轮骰子的点数之和判断。

最终返回dp数组即可。

总结

本题考查动态规划。难度系数困难。难点在于状态转移方程的推导以及实现成代码。

复杂度方面，中层循环的长度取决于上一轮循环的个数5n + 1 ，最终的时间复杂度是O(n^2) ，辅助数组的最大长度是5n - 4 ，因此空间复杂度是O(n) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/ozzl1r/