剑指offer60 n个骰子的点数【DP】
题目描述
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
1 | 输入: 1 |
示例 2:
1 | 输入: 2 |
限制:
1 | 1 <= n <= 11 |
解题思路
方法一:动态规划
$$
f(n,x)=\sum^{6}_{1}f(n-1,x-i)✖\frac{1}{6}
$$
代码实现
1 | class Solution60 { |
复杂度分析
时间复杂度:O($n ^ 2$)
空间复杂度:O(n)
资料
剑指offer60 n个骰子的点数【DP】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.