题目描述

把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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

我感觉这个就是考察概率论，最快的方式一个就是你知道公式，然后按照公式去写算法？？？
似乎不太对，确实想了一下，公式也不太好推，还是DP?
但是你要是不知道公式，那你就只能自己去推每种情况可能出现的次数，然后除以总的情况数，作为一个结果

先从最容易想出来的暴力求解看：
一次投掷会有六种可能：123456
n次投掷会有 6^n 种可能的组合

但是可能会有和为重复的，根据取值范围来看是[n,6n]种，即5n+1种和的结果
image.png

然后就可以发现，暴力法的时间复杂度太高，指数级上升。O(6^n)

所以必须换更精简的方法求解，
那我们来分析一下这个题是否适用于动态规划的求解方法

1.重叠子问题；
怎么去分解这个问题？
可以在一次一次投掷的过程中分解点数的求解，投一次，6种点数，投第二次，在第一次的基础上和他进行组合相加，第三次依次类推
2.最优子结构；
那么这个问题是否具有最优子结构呢？
这个其实并不完全是一个求最值的信息，但不影响我们用这个来做，因为每一步都是精确而唯一的。
3.状态转移方程，
那怎么转移呢？
假设已知n−1 个骰子的解 f(n - 1) ，此时添加一枚骰子，求 n 个骰子的点数和为 x 的概率 f(n, x)
image.png

但，到这还没结束，因为会存在越界的问题，核心解法已经确定，因为越界问题会导致在采用递归这类求解方法时，边界条件处理繁琐
所以可以换种思路，采用正向递推的方式
可以参考此题解：
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/

image.png

算法代码：

然后写代码的时候要注意一下分母什么的会不会越界，毕竟分母还是指数级上涨

  1. class Solution {
  2. public:
  3.     vector<double> dicesProbability(int n) {
  4.         vector<double> dp(6,1.0/6.0);
  5.         for(int i=2;i<=n;i++){
  6.             vector<double> tmp(5*i+1,0);
  7.             for(int j =0;j<dp.size();j++){
  8.                 for(int k =0;k<6;k++){
  9.                     tmp[j+k] += dp[j]/6;
  10.                 }
  11.             }
  12.             dp = tmp;
  13.         }
  14.         return dp;
  15.     }
  16. };

复杂度分析：

时间复杂度，由于最内层k循环是有限次数，所以一共是O(n^2)
空间复杂度: 需要两个一维的dp数组，O(n)