题目描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

题解

本题的题目为求n个骰子的点数出现的概率，这里的点数指的是投掷完n个骰子后，各个和出现的次数，使用浮点数组表示，其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个点数的概率。

我们需要算出所有点数出现的次数，最后除以所有点数出现的总次数即可得到概率，所有点数出现的总次数可以直接算出来，即6的n次方。使用动态规划的思想，这里假设一个dp[n][s]为骰子数为n，和为s的情况。当有n个骰子时，点数从n取到6n（解释一下，当有n个骰子时，最小点数为n个骰子全掷为1的情况，此时点数为n；最大点数为n个骰子全掷为6的情况，此时点数为6n）。

于是，可以得到状态转移方程：

当n = 1时，dp[1][s] = 1，其中s = 1,2,3,4,5,6。

当n > 1时，dp[n][s] = dp[n-1][s-1]+dp[n-1][s-2]+dp[n-1][s-3]+dp[n-1][s-4]+dp[n-1][s-5]+dp[n-1][s-6]，其中s in [n, 6n]。

例如，投掷n=2个骰子时，点数s=7出现的次数相当于n-1个骰子投掷出2和5的次数、3和4的次数、1和6的次数之和，而点数1, 2, 3, 4, 5, 6出现的次数都是1，故投掷2个骰子时点数7出现的次数是6。

得到点数出现的次数之后的问题就稍微简单一些了，将点数除以所有点数出现的总次数就可以得到概率了。

下面是参考代码：

class Solution {
    // 定义maxValue为6，方便以后进行扩展
    int maxValue = 6;
    public double[] twoSum(int n) {
        if (n < 1)
            return new double[] {};
        double[][] dp = new double[n+1][maxValue*n+1];

        // 边界处理
        for (int i = 1; i <= maxValue; i++)
            dp[1][i] = 1;

        // 当n > 1时，dp[n][s] = dp[n-1][s-1]+dp[n-1][s-2]+dp[n-1][s-3]+dp[n-1][s-4]+dp[n-1][s-5]+dp[n-1][s-6]，其中s in [n, 6n]
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= maxValue*n; j++) {
                for (int k = 1; k <= maxValue; k++) {
                    if (j > k)
                        dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        double all = Math.pow(6, n);
        double[] res = new double[maxValue*n-n+1];
        int index = 0;
        for (int i = n; i <= maxValue*n; i++) {
            res[index++] = dp[n][i] / all;
        }
        return res;
    }
}