60.n个骰子的点数.md

60.n个骰子的点数

题目

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

思路 & 解答

如果使用暴力法，每一个骰子扔到 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;
    }
};