【LeetCode】【剑指offer】【n个骰子的点数】

剑指 Offer 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 <= n <= 11

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一个骰子的概率

这是两个骰子的概率 

也就是说我们一个的骰子产生的结果分别为1,2,3,4,5,6

而我们两个 骰子产生的结果分别为2,3,4,5,6,7,8,9,10,11,12，

其中2的概率与一个骰子中的1的概率有关，

3的概率与一个骰子中的1,2的概率有关，

4的概率与一个骰子中的1,2,3的概率有关

5的概率与一个骰子中的1,2,3,4的概率有关

6的概率与一个骰子中的1,2,3,4,5的概率有关

7的概率与一个骰子中的1,2,3,4,5,6的概率有关

8的概率与一个骰子中的2,3,4,5,6的概率有关

9的概率与一个骰子中的3,4,5,6的概率有关

10的概率与一个骰子中的4,5,6的概率有关

11的概率与一个骰子中的5,6的概率有关

12的概率与一个骰子中的6的概率有关

下面是三颗骰子的情况

 

 

 

 

 

 

 

 对于上面的结果我们拿两颗骰子投出3来举例，3的话需要原来的一个骰子投出1或2，也就是1/6和1/6的概率，并且需要我们第二颗骰子投出对应的2和1，也就是1/6和1/6的概率，对应的情况相乘，就能得到1/36和1/36的概率。

如果是三颗骰子我们想要投出3的话，我们就需要前面的两颗骰子都是投出2的情况再乘上我们第三颗骰子投出1的概率，也就是1/36再乘上1/6也就是1/216的概率。

 所以我们只需要将我们上一次骰子的结果除以6然后再一个新的长度为5*i+1的容器中，从头开始遍历我们上一次的骰子的结果个数次，将我们的数据按照上面的形式相加，然后迭代n-1轮，就能够得到我们想要的结果

class Solution {
public:
    vector<double> dicesProbability(int n) {
        //创建一个初始的一个骰子的结果，就是6个1/6的概率
        vector<double> result (6,1.0/6.0);
        //由于一个骰子的结果我们初始就是，所以我们下面计算2个及以上的骰子形成的概率
        for(int i=2;i<=n;i++)
        {
            //创建一个大小为5*i+1的容器，也就是我们的n个骰子的结果个数作为容器的大小
            //每增加一个骰子就会增加6情况，减少1种情况
            vector<double> tmp(5*i+1);
            for(int j=0;jsize();j++)
            {
                for(int k=0;k<6;k++)
                {
                    //将我们原有的概率总数除以6
                    //因为要是不考虑重复结果的话，1个骰子有6种情况
                    //两个骰子有36种情况，以此类推
                    tmp[j+k]+=result[j]/6.0;
                }
            }
            //迭代我们的result
            result=tmp;
        }
        return result;
    }
};