这篇文章主要介绍了LeetCode如何求n个骰子的点数,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
(1/6)*(1/6)=1/36
, 只有 1+1 一种情况; 而点数之和为 3 的概率是
1/36+1/36=1/18
, 有 1+2 和 2+1 两种情况, 以此类推{点数和:概率}
, 那么对于 n+1 而言, 我们只需要对每个点数之和加上 1~6 作为新的点数之和, 将原有概率乘以 1/6 累加到新的点数和对应的概率上即可6*n
(每个骰子点数都是 6)5N*6
个数import collections
class Solution:
def twoSum(self, n: int) -> List[float]:
# DP, dp为当前的点数和=>概率的字典, 初始化dp[0] = 1, 代表0个骰子时点数之和为0的概率为1
# 增加一个骰子后, 我们只需要对原来字典的每个点数之和加上 1~6 作为新的点数之和, 并将原有概率乘以 1/6 累加到新的点数和对应的概率上即可
dp = {}
dp[0] = 1
for i in range(1, n + 1):
newdp = collections.defaultdict(int)
for sm in dp:
for v in range(1, 7):
# 增加一个骰子后, 累加其概率到新的点数和上
newdp[sm + v] += dp[sm] / 6
dp = newdp
res = []
for sm in range(n, 6 * n + 1):
# 将值依次存入结果中
res.append(dp[sm])
return res
感谢你能够认真阅读完这篇文章,希望小编分享的“LeetCode如何求n个骰子的点数”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。