剑指OfferV2(增) -- n个骰子的点数

Part0前言

剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 刷题仓库介绍：刷题仓库：CodeSolution 编程知识库：https://github.com/Damaer/Coding 文档地址：https://damaer.github.io/Coding/#/ 剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~

Part1n个骰子 🎲 的点数

1题目

把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]

2思路 & 解答

如果使用暴力法，每一个骰子扔到 1 - 6 的概率都是 1/6, 如果有 n 个 骰子，先不看重复的情况，一共有 6^n^ 种情况，点数的范围是 n ~ 6n ，也就是 5n+1 种。

但是以上的计算复杂度实在太高，我们不能接受。

其实，这道题可以用动态规划来处理， 1 个骰子的情况是已知的，而 2 个骰子的情况呢？2 个骰子的情况，可以使用 1 个骰子的情况推出， 3 个骰子的情况，可以使用 2 个骰子的结果推出...

假设n个骰子的解释f(n)，n个骰子扔出点数和为x的概率为f(n,x)

假设我们已经计算出 n-1 个骰子扔出的点数和以及概率 f(n-1)，现在加一个骰子，一共有 n 个骰子，f(n) 怎么求呢？

我们现在就只求 f(n,x):

1. 如果第 n 个骰子扔出的是 1，那么剩下的 n-1 个骰子扔出的应该是 x-1,概率为 f(n-1,x-1)
2. 如果第 n 个骰子扔出的是 2，那么剩下的 n-1 个骰子扔出的应该是 x-2,概率为 f(n-1,x-2)
3. 如果第 n 个骰子扔出的是 3，那么剩下的 n-1 个骰子扔出的应该是 x-3,概率为 f(n-1,x-3)
4. 如果第 n 个骰子扔出的是 4，那么剩下的 n-1 个骰子扔出的应该是 x-4,概率为 f(n-1,x-4)
5. 如果第 n 个骰子扔出的是 5，那么剩下的 n-1 个骰子扔出的应该是 x-5,概率为 f(n-1,x-5)
6. 如果第 n 个骰子扔出的是 6，那么剩下的 n-1 个骰子扔出的应该是 x-6,概率为 f(n-1,x-6)

所以，f(n,x) 应该是上面的概率加起来，f(n,x) = (f(n-1,x-1)+ f(n-1,x-2) +f(n-1,x-3)+f(n-1,x-4)+f(n-1,x-5)+f(n-1,x-6))* 1/6。注意，最后一个骰子扔出每一种的概率都是 1/6。

那么我们的程序应该是从 1 个骰子模拟增加到 n 个骰子，不断计算出概率。

Java 代码实现如下:

class Solution {

    public double[] twoSum(int n) {
        double pre[] = {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
        for (int i = 2; i <= n; i++) {
            double temple[] = new double[5 * i + 1];
            for (int j = 0; j < pre.length; j++)
                for (int x = 0; x < 6; x++)
                    temple[j + x] += pre[j] / 6;
            pre = temple;
        }
        return pre;
    }
};

C++ 代码如下：

class Solution {
public:
    vector<double> twoSum(int n) {
        vector<double> pre = {1.0/6, 1.0/6, 1.0/6, 1.0/6, 1.0/6, 1.0/6};
        for(int i = 2; i <= n;i++){
            vector<double> temple(5*i+1,0);
            for(int j = 0;j < pre.size();j++){
                for(int k=0;k<6;k++){
                    temple[j+k] += pre[j]*1.0/6; 
                }
            }
            pre = temple;
        }
        return pre;
    }
};

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作