leetcode [面试题60] n个骰子的点数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1:

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

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：

1 <= n <= 11

来自题解:

我们发现，我们只需要用一个数组cnts，cnts[i] 表示掷出i的次数，那么cnts[i] 就等于前面六个相加，或者前面五个相加，或者。。。。

为了简单起见，我们从后往前遍历，这样我们的逻辑可以统一为 cnts[i] 就等于前面六个cnts[j]相加，其中j等于i - 1, i - 2, i - 3, i - 4, i - 5, i - 6。

如果使用迭代，我们只需要迭代n - 1次，每次迭代相当于一次投掷，而内层循环的逻辑就是上面提到的，我们每次投掷都去更新cnts[i]

class Solution:
    def twoSum(self, n: int) -> List[float]:
        if n == 0:
            return []
        cnts = [0] + [1] * 6 + [0] * (6 * n - 6)

        for _ in range(n - 1):
            for i in range(6 * n, 0, -1):
                cnts[i] = sum(cnts[max(i - 6, 0): i])

        return filter(lambda a: a != 0, list(map(lambda a: a / 6 ** n, cnts)))