温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode如何求n个骰子的点数

发布时间:2021-12-15 13:56:25 来源:亿速云 阅读:128 作者:小新 栏目:大数据

这篇文章主要介绍了LeetCode如何求n个骰子的点数,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

题目描述

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

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

  • 1 <= n <= 11
                     

题目样例

                     

示例

  • 输入: 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. 可以根据 n 个骰子的概率推导出 n+1 个骰子的概率吗
                     

解决方案

                     
思路
  • 分析题目, 先从 1 个骰子的最简单情况出发, 显然点数为 1~6 的概率都是 1/6
  • 那如果是 2 个骰子呢? 假设第一个骰子点数为 1, 第二个可以是 1~6, 两者之和就是 2~7; 而如果第一个点数为 2, 那么两者之和就是 3~8, 以此类推
  • 显然 2 个骰子点数之和为 2 的概率是                         (1/6)*(1/6)=1/36, 只有 1+1 一种情况; 而点数之和为 3 的概率是                         1/36+1/36=1/18, 有 1+2 和 2+1 两种情况, 以此类推
  • 所以如果我们使用一个字典来保存当前骰子数 n 的每个点数之和的概率, 即键值对是                         {点数和:概率}, 那么对于 n+1 而言, 我们只需要对每个点数之和加上 1~6 作为新的点数之和, 将原有概率乘以 1/6 累加到新的点数和对应的概率上即可
  • 最后只需要根据有效点数之和从小到大, 将字典中的值依次存入最终结果中
  • 对于 n 个骰子而言, 其点数之和最小为 n (每个骰子点数都是 1), 最大为                         6*n (每个骰子点数都是 6)
  • 下面代码对必要的步骤有详细的解释, 方便大家理解
                     
复杂度
  • 时间复杂度 O(N^2): 两层循环, 外层遍历 N 个数, 内层遍历                         5N*6 个数
  • 空间复杂度 O(N): 字典中需要存 5N 个键值对
                     
代码
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个骰子的点数”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI