剑指 Offer 60. n个骰子的点数

这是我参与8月更文挑战的第9天，活动详情查看：8月更文挑战

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

解题思路

掷出的点数的概率=组成该点数的情况之和/所有情况的数量

所有情况的数量=6的n次方（n为骰子的个数）

所以我们只需要计算每个点数的出现次数，就可以求出掷出该点数的概率

数组定义

dp[i][j]代表使用i个骰子，产生的点数为j的情况个数

初始化

一粒骰子的时候只能产生一到六的点数，并且每种点数的可能为1

        dp[1][1]=1;
        dp[1][2]=1;
        dp[1][3]=1;
        dp[1][4]=1;
        dp[1][5]=1;
        dp[1][6]=1;
复制代码

状态转移

dp[i][j]由i-1个骰子的情况转移而来，因为第i个骰子的可能点数为1到6，所以由dp[i-1][j-k]转移而来（k为第i颗骰子可能掷出的点数）

for (int k=1;k<=6;k++)
         if(j-k>=0)
             dp[i][j]+=dp[i-1][j-k];
复制代码

代码

class Solution {
    public double[] dicesProbability(int n) {


        int[][] dp = new int[n + 1][6 * n + 1];
        dp[1][1]=1;
        dp[1][2]=1;
        dp[1][3]=1;
        dp[1][4]=1;
        dp[1][5]=1;
        dp[1][6]=1;

        int cnt=0;
        for (int i=2;i<=n;i++)
        {
            for (int j=i;j<=6*i;j++)
            {
                for (int k=1;k<=6;k++)
                    if(j-k>=0)
                        dp[i][j]+=dp[i-1][j-k];
            }
        }

        double v = Math.pow(6 , n);
        double[] res = new double[5 * n + 1];
        for (int i=n,j=0;i<=6*n;i++,j++)
        {
            res[j]=dp[n][i]/v;
        }
        return res;
    }
}
复制代码