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

godweiyang

发布于 2020-04-14 09:06:50

5110

发布于 2020-04-14 09:06:50

文章被收录于专栏：算法码上来算法码上来

题目链接

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/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度