60.n个骰子的点数

raylan.chen大约 2 分钟

class Solution {
    double[] res;
    public double[] statisticsProbability(int num) {
        // 回溯
        // n个色子，n个循环
        if (num == 0) return new double[0];
        res = new double[num * 6 - num + 1];
        double pro = 1.0;
        // 注意 1 / 6 = 0
        for (int i = 0; i < num; i++) {
            pro *= 1.0 / 6;
        }
        int index = 0;
        int sum = 0;
        recusion(num, index, pro, sum);
        return res;
    }

    public void recusion(int num, int index, double pro, int sum) {
        if (index == num) {
            res[sum - num] += pro;
            return;
        }
        for (int i = 1; i <= 6; i++) {
            index++;
            sum += i;
            recusion(num, index, pro, sum);
            // 回溯
            sum -= i;
            index--;
        }
    }
}

优秀题解

class Solution {
    public double[] statisticsProbability(int num) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= num; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/637778/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

1、第一个循环：骰子个数

2、第二个循环：第一个骰子总和

例如：1，2，3，4，5，6——总共6个

3、第三个循环：第一个骰子 + 第二个骰子总和

例如：2，3，4，5，6，7，8，9，10，11，12——总共11个

4、第二个循环，「第一个骰子（继承上一个循环）」总和：2，3，4，5，6，7，8，9，10，11，12

5、第三个循环，「第二个骰子」总和：3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18——总共16个

......

第二个循环可以继承上一次循环的结果，随后运算再加一个骰子的总和结果

60.n个骰子的点数

60.n个骰子的点数

参考链接

个人尝试

优秀题解