【重点】【DP】剑指offer——面试题43：n个骰子的点数

力扣185
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
思路分析（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/）

Python

class Solution:
    def statisticsProbability(self, num: int) -> List[float]:
        res = [0] * (num * 5 + 1) # 和范围[num, 6num], 共计5num+1种可能
        dp = [[0] * (num*6 + 1) for _ in range(num+1)] # dp[i][j]表示i个骰子，和为j概率
        for i in range(1, 7):
            dp[1][i] = 1/6
        for i in range(2, num+1):
            for j in range(i, i*6 + 1):
                for k in range(1, 7):
                    if j > k:
                        dp[i][j] += dp[i-1][j-k] * (1/6)
        for i in range(0, num*5 + 1):
            res[i] = dp[num][i+num] # 和范围[num, 6num]
        return res

Java

class Solution {
    public double[] statisticsProbability(int num) {
        double[] res = new double[num * 5 + 1];           // 和的范围[n, 6n], 共计5n+1个
        double[][] dp = new double[num + 1][num * 6 + 1]; // dp[i][j]表示i个骰子，和为j的概率
        for (int i = 1; i <= 6; ++i) {
            dp[1][i] = 1.0/6.0;
        }
        for (int i = 2; i <= num; ++i) {        // 骰子数量
            for (int j = i; j <=i * 6; ++j) {   // i个骰子的和
                for (int k = 1; k <= 6; ++k) {  // 递推关系
                    if (j > k) {
                        dp[i][j] += dp[i - 1][j - k] / 6.0;
                    }
                }
            }
        }

        for (int i = 0; i < num * 5 + 1; ++i) {
            res[i] = dp[num][i + num];
        }
        return res;
    }
}

// 写法1
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;
    }
}

// 写法2
class Solution {
    public double[] statisticsProbability(int num) {
        double[] res = new double[6];         // 只有1个数字时的结果
        Arrays.fill(res, 1.0 / 6.0);
        for (int i = 2; i <= num; ++i) {
            double[] dp = new double[i * 5 + 1]; // 从i -> i * 6
            for (int j = 0; j < res.length; ++j) {
                for (int k = 0; k < 6; ++k) {
                    dp[j + k] += res[j] / 6.0;
                }
            }

            res = dp;
        }

        return res;
    }
}