本文共 2313 字，大约阅读时间需要 7 分钟。

题目描述

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

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

示例 1:

输入: 1

输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java

1. 确定问题解的表达式。可将f(n, s) 表示n个骰子点数的和为s的排列情况总数
2. 确定状态转移方程。n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！那么有：f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)
   3.上面就是状态转移方程，已知初始阶段的解为：当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

class Solution {
       public double[] dicesProbability(int n) {
                   //dp[i][j]表示i个筛子，点数为j的排列总数        int dp[][]=new int[n+1][6*n+1];        double [] res=new double[5*n+1];  //点数和范围 n-6n        double all=Math.pow(6,n);        //动态规划表初始化        for(int i=1;i<=6;i++)            dp[1][i]=1;        //f(n,s)=f(n-1,s-1)+f(n-1,s-2)f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)        for(int i=1;i<=n;i++){
               for(int j=i;j<=6*n;j++){
                   for (int k=1;k<=6;k++){
                       dp[i][j]+=(j>=k)?dp[i-1][j-k]:0;                    if(i==n)                        res[j-i]=dp[i][j]/all;                }                               }                        }        return  res;            }}

优化成一维数组

class Solution {
       public double[] dicesProbability(int n) {
           //由于每个dp[i][j]只于i-1时刻的状态有关，所以可以删去一个维度，        if(n==0)  return new double[0];        int dp[]=new int[6*n+1];        double [] res=new double[5*n+1];  //点数和范围 n-6n        double all=Math.pow(6,n);        //动态规划表初始化        for(int i=1;i<=6;i++){
                dp[i]=1;             res[i-1]=1.0/6;        }                   //f(n,s)=f(n-1,s-1)+f(n-1,s-2)f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)        for(int i=2;i<=n;i++){
               for(int j=6*n;j>=1;j--){
     //第二个循环从后往前遍历，**避免覆盖**                int temp=0;                for (int k=1;k<=6;k++){
                      temp+=(j>=k)?dp[j-k]:0;                }                dp[j]=temp;                if(i==n && j>=n){
                           res[j-i]=dp[j]/all;               }                               }             }        return  res;            }}