这题出自LeetCode,题目如下:
把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
首先,容易发现这是一道动态规划的题,里面每一种可能性太多了,且为了计算每一种可能性,里面相互重叠的部分非常多,必然存在着大量重复的计算,而动态规划本质就是为了避免子可能性的重复计算而提出的算法。那么,接下来,我们要思考如何将问题进行拆分成子问题,并且通过解决子问题就可以快速得到问题本身的答案。