统计结果概率

难度: Medium

你选择掷出 num 个色子，请返回所有点数总和的概率。

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

示例 1：

输入：num = 3
输出：[0.00463,0.01389,0.02778,0.04630,0.06944,0.09722,0.11574,0.12500,0.12500,0.11574,0.09722,0.06944,0.04630,0.02778,0.01389,0.00463]

示例 2：

输入：num = 5
输出:[0.00013,0.00064,0.00193,0.00450,0.00900,0.01620,0.02636,0.03922,0.05401,0.06944,0.08372,0.09452,0.10031,0.10031,0.09452,0.08372,0.06944,0.05401,0.03922,0.02636,0.01620,0.00900,0.00450,0.00193,0.00064,0.00013]

提示：

1 <= num <= 11

Submission

运行时间: 36 ms

内存: 15.1 MB

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        # dp[n][s]表示投第n个骰子时，点数和为s的次数
        dp = [[0] * (6*n+1) for _ in range(1, 67)]
        for i in range(1, 7):
            dp[1][i] = 1

        for i in range(2, n+1):
            for j in range(i, i*6+1):
                for k in range(1, 7):
                    dp[i][j] += dp[i-1][j-k]

        res = []
        for i in range(n, n*6+1):
            res.append(dp[n][i]*1./6**n)
        return res

Explain

本题解采用动态规划的方法解决多个骰子掷出的点数概率问题。定义dp数组，其中dp[i][s]表示投掷第i个骰子时，所有骰子点数和为s的出现次数。初始化第一个骰子的结果，即每个点数出现一次。对于之后的每个骰子，更新dp数组，考虑上一个骰子的点数和，加上当前骰子可能的点数（1至6），来更新当前骰子的点数和出现次数。最后，计算每个可能的点数和出现的概率，即每个点数和出现次数除以总的可能组合数（6^n）。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        # dp[n][s]表示投第n个骰子时，点数和为s的次数
        dp = [[0] * (6*n+1) for _ in range(1, 67)]
        for i in range(1, 7):
            dp[1][i] = 1  # 初始化第一个骰子的每个面的出现次数

        for i in range(2, n+1):
            for j in range(i, i*6+1):
                for k in range(1, 7):
                    dp[i][j] += dp[i-1][j-k]  # 从前一个骰子的状态转移而来

        res = []
        for i in range(n, n*6+1):
            res.append(dp[n][i]*1./6**n)  # 计算每个点数和的概率
        return res

Explore

在动态规划中，初始化第一个骰子的结果是因为只有一个骰子的情况下，它的点数和只能是1到6，这是确定的。这个初始化设置为基础，后续的所有骰子结果都是基于前一个骰子的结果推导出来的。如果初始化所有骰子，就需要预先知道所有骰子的所有组合，这是不现实的，而且计算上非常复杂。因此，动态规划的方法是从已知的简单情况出发，逐步推导复杂情况的有效策略。

在更新dp数组时，i到i*6的遍历范围代表的是投掷i个骰子可能出现的点数和的最小值和最大值。最小值i是因为每个骰子至少贡献1点，而最大值i*6则是每个骰子都投出6点的情况。这个范围确保了考虑了所有可能的点数和，保证了数据的完整性和正确性。

在内层循环中，使用`dp[i-1][j-k]`确实可能出现`j-k`小于i-1的情况，这时`dp[i-1][j-k]`是没有意义的，因为点数和至少为i-1（每个骰子至少贡献1点）。在这个程序中，通过检索的下标始终保持在有效范围内（即j-k >= i-1），确保了程序的正确性。如果j-k小于i-1，则这部分的贡献是0，不会被加到`dp[i][j]`中，从而不会影响结果的正确性。

这种计算方法是准确的。`dp[n][i]`中存储的是投掷n个骰子得到点数和为i的所有可能的情况的数量。由于每个骰子有6个面，投掷n个骰子的总组合数是`6^n`。因此，计算点数和为i的概率即为这一点数和出现的次数除以总的组合数，即`dp[n][i] / 6^n`。这样确保了考虑到了所有n个骰子的组合情况。