专栏首页算法码上来【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!

【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!

题目链接

LeetCode 面试题60. n个骰子的点数[1]

题目描述

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

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

说明:

  • 1 <= n <= 11

示例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]

题解

令 表示投掷 个骰子,点数为 的方法数。那么可以根据最后一个骰子的点数情况( 到 ),递归进行计算:

当然还得加一些约束,例如 个骰子的点数范围是 ,所以一定有 ,即 。所以综上 的范围是 ,最后的转移方程就是:

但是,考虑到在计算 个骰子时,如果 ,那么 ,也就是 是根本不会被计算的。所以初始化的时候如果都是 ,那么就不用管这个下界了,也就是转移方程为:

此外,因为每次计算只会用到 个骰子的方法数,所以第一个维度可以省去。但是注意计算的时候 就得逆序遍历了,这样才不会覆盖掉 个骰子的方案数,造成后面的计算错误。

最后答案就是 。

代码

动态规划+空间优化(c++)

class Solution {public:    vector<double> twoSum(int n) {        vector<int> dp(6*n+1, 0);        for (int i = 1; i <= 6; ++i) dp[i] = 1;        for (int i = 2; i <= n; ++i) {            for (int s = 6*i; s >= i; --s) {                dp[s] = 0;                for (int j = 1; j <= min(6, s-i+1); ++j) {                    dp[s] += dp[s-j];                }            }        }        double total = pow(6, n);        vector<double> res;        for (int s = n; s <= 6*n; ++s) {            res.push_back(dp[s]/total);        }        return res;    }};

参考资料

[1]

LeetCode 面试题60. n个骰子的点数: https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?

    在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

    godweiyang
  • 每日一题[LeetCode 315]计算右侧小于当前元素的个数

    给定一个整数数组nums,按要求返回一个新数组counts。数组counts有该性质:counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。

    godweiyang
  • 【每日算法Day 77】LeetCode 第 181 场周赛题解

    https://leetcode-cn.com/contest/weekly-contest-181

    godweiyang
  • Objective-C基础知识

    1.标示符:字母、下划线、美元符号和数字组成,字母和下划线美元符号开头,区分大小写 2.代码区存放代码,数据区存放静态变量和字符串常量,栈存放局部变量,堆存放...

    苦咖啡
  • 第2章 变量和基本类型

    用户1653704
  • 2019-6-1-UML类图

    UML类图(Class Diagrams)是一种面向对象分析和设计中,描述被分析系统中各个组成部分之间相互关系的图形。

    黄腾霄
  • [WPF]为什么使用SaveFileDialog创建文件需要删除权限?

    好像很少人会遇到这种需求。假设有一个文件夹,用户有几乎所有权限,但没有删除的权限,如下图所示:

    dino.c
  • 团体程序设计天梯赛-练习集 L1-022 奇偶分家

    C you again 的博客
  • 2.C++中的bool类型,三目运算符,引用

    在C++中,bool类型只有true(非0)和flase(0)两个值,且bool类型只占用了一个字节.

    张诺谦
  • 巧用拦截器:高效的扩展点设计

    最近在设计框架时,需要设计一类扩展点,发现不能简单地继承或使用事件来给使用者提供 API。最终使用拦截器模式解决了 API 的设计。 扩展点使用场景 ...

    用户1172223

扫码关注云+社区

领取腾讯云代金券