题目描述
把 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 - 6 的概率都是 1/6，如果有 n 个 骰⼦，先不看重复的情况，⼀共有 6n 种情况，点数的范围是 n ~ 6n，也就是 5n+1 种。
时间复杂度：O(6ⁿ)，每个骰子有6种可能，n个骰子组合数为6ⁿ
空间复杂度：O(n)，递归调用栈的深度
以上的计算复杂度实在太⾼，我们不能接受。
动态规划（推荐）
其实，这道题可以⽤动态规划来处理， 1 个骰⼦的情况是已知的，⽽ 2 个骰⼦的情况呢？ 2 个骰⼦的情况，可以使⽤ 1 个骰⼦的情况推出， 3 个骰⼦的情况，可以使⽤ 2 个骰⼦的结果推出…
dp[i][j]表示i个骰子和为j的出现次数
执行过程示例（n=2）：
时间复杂度：O(n²)，外层循环n次，内层循环最多6n次
空间复杂度：O(n²)，需要二维数组存储中间结果
空间优化动态规划
通过观察发现当前状态只依赖前一个状态，可以优化空间。通过滚动数组减少空间使用
时间复杂度：O(n²)，外层循环n次，内层循环最多6n次
空间复杂度：O(n)，只保留前一轮的结果，空间从O(n²)降到O(n)
数学公式法（多项式展开）
和为s的概率对应于(x+x²+…+x⁶)ⁿ展开式中xˢ的系数
时间复杂度：O(n²)，多项式乘法计算
空间复杂度：O(n)，存储多项式系数