剑指offer | 面试题47：n个骰子的点数

“Leetcode : https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_47_dicesProbability/Solution.java

剑指 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]

方法一：暴力法

给定n个骰子，可得:

• 每个骰子摇到1至6的概率相等，都为1/6
• 将每个骰子的点数看作独立情况，共有6n种「 点数组合」。例如n = 2时的点数组合为：(1,1),(1,2)... ,(2, 1),(2,2),，.. ,(6,1),... ,(6,6)
• n个骰子「点数和」的范围为[n, 6n]，数量为6n-n+1=5n+ 1种。暴力统计：每个「 点数组合」都对应一个「点数和」，考虑遍历所有点数组合,统计每个点数和的出现次数,最后除以点数组合的总数(即除以6n )，即呵得到每个点数和的出现概率。

“如下图所际，为输入n=2时，点数组合、点数和、各点数概率的计算过程。

暴力法需要遍历所有点数组合，因此时间复杂度为 O(6^n) ，观察本题输入取值范围 1≤n≤11

方法二：动态规划

设输入 n个骰子的解（即概率列表）为 f(n) ，其中「点数和」 x 的概率为 f(n, x) 。

假设已知n - 1个骰子的解f(n - 1)，此时添加一枚骰子，求n个骰子的点数和为x的概率f(n, x) 当添加骰子的点数为1时，前n- 1个骰子的点数和应为x- 1，可组成点数和x ;同理，当此骰 子为2时,前n-1个骰子应为x- 2 ;以此类推，直至此骰子点数为6。将这6种情况的概率相加，即可得到概率f(n. x)。递推公式如下所示：

根据以上分析,知通过子问题的解f(n- 1)可递推计算出f(n)，而输入一个骰子的解f(1)已知,因此可通过解f(1)依次递推出任意解f(n)。如下图所际，为n=2,x= 7的递推计算示例。

观察发现，以上递推公式虽然可行，但f(n- 1,x- i)中的x- i会有越界问题。例如，若希望递推计 算f(2,2),由于一个骰子的点数和范围为[1,6] ，因此只应求和f(1,1)，即f(1,0)，f(1,-1)...f(1,-4)皆无意义。此越界问题导致代码编写的难度提升。

“如下图所示，以上递推公式是“逆向”的，即为了计算f(n,x)，将所有与之有关的情况求和;而 倘若改换为“正向”的递推公式，可解决越界问题。

具体来看，由于新增骰子的点数只可能为1至6，因此概率f(n-1,x)仅与f(n,x+ 1), f(n,x + 2), ... f(n,x +6)相关。而，遍历f(n- 1)中各点数和的概率,并将其相加至f(n)中所有相关项，即可完成f(n- 1)至f(n)的递推。

“将f(i)记为动态规划列表形式dp[i，则i= 1, 2, ... n的状态转移过程如下图所示。

复杂度分析：

• 时间复杂度O(n^2 )
• 空间复杂度O(n)

代码：通常做法是声明一个二维数组dp，dp [i] [j] 代表前i个骰子的点数和j的概率,并执行状态转移。而 于dp[i]仅由dp[i-1]递推得出，为降低空间复杂度，只建立两个一维数组dp,tmp交替前进即可。

public double[] dicesProbability(int n) {
        //因为最后的结果只与前一个动态转移数组有关，所以这里只需要设置一个一维的动态转移数组
        //原本dp[i][j]表示的是前i个骰子的点数之和为j的概率，现在只需要最后的状态的数组，所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率。
        //初始是1个骰子情况下的点数之和情况，就只有6个结果，所以用dp的初始化的size是6个
        double[] dp = new double[6];
        //只有一个数组
        Arrays.fill(dp,1.0/6.0);
        //从第2个骰子开始，这里n表示n个骰子，先从第二个的情况算起，然后再逐步求3个、4个···n个的情况
        //i表示当总共i个骰子时的结果
        for(int i=2;i<=n;i++){
        //每次的点数之和范围会有点变化，点数之和的值最大是i*6，最小是i*1，i之前的结果值是不会出现的；
        //比如i=3个骰子时，最小就是3了，不可能是2和1，所以点数之和的值的个数是6*i-(i-1)，化简：5*i+1
            //当有i个骰子时的点数之和的值数组先假定是temp
            double[] temp = new double[5*i+1];
            //从i-1个骰子的点数之和的值数组入手，计算i个骰子的点数之和数组的值
            //先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的temp[j+k]的值
            for(int j=0;j<dp.length;j++){
            //比如只有1个骰子时，dp[1]是代表当骰子点数之和为2时的概率，它会对当有2个骰子时的点数之和为3、4、5、6、7、8产生影响，因为当有一个骰子的值为2时，另一个骰子的值可以为1~6，产生的点数之和相应的就是3~8；比如dp[2]代表点数之和为3，它会对有2个骰子时的点数之和为4、5、6、7、8、9产生影响；所以k在这里就是对应着第i个骰子出现时可能出现六种情况，这里可能画一个K神那样的动态规划逆推的图就好理解很多
                for(int k=0;k<6;k++){
                    //这里记得是加上dp数组值与1/6的乘积，1/6是第i个骰子投出某个值的概率
                    temp[j+k]+=dp[j]*(1.0/6.0);
                }
            }
            //i个骰子的点数之和全都算出来后，要将temp数组移交给dp数组，dp数组就会代表i个骰子时的可能出现的点数之和的概率；用于计算i+1个骰子时的点数之和的概率
            dp = temp;
        }
        return dp;
    } 

参考链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d

END