n个骰子的点数

这题出自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

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wppjzy.html