优化自己的网站软文广告代理平台
剑指 Offer 60. n个骰子的点数
难度：middle\color{orange}{middle}middle
题目描述
把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<=111 <= n <= 111<=n<=11
算法
(动态规划)
设输入 n 个骰子的解（即概率列表）为 f(n) ，其中「点数和」 x 的概率为 f(n,x) 。
假设已知 n−1 个骰子的解 f(n−1) ，此时添加一枚骰子，求 n 个骰子的点数和为 x 的概率 f(n,x) 。
当添加骰子的点数为 1 时，前 n−1 个骰子的点数和应为 x−1 ，方可组成点数和 x ；同理，当此骰子为 2 时，前 n−1 个骰子应为 x−2 ；以此类推，直至此骰子点数为 6 。将这 6 种情况的概率相加，即可得到概率 f(n,x) 。递推公式如下所示：
f(n,x)=∑i=16f(n−1,x−i)∗1/6f(n, x) = \sum_{i=1}^6f(n - 1, x - i) * 1 / 6f(n,x)=∑i=16f(n−1,x−i)∗1/6
复杂度分析
-
时间复杂度：O(n2)O(n^2)O(n2)
-
空间复杂度 : O(n)O(n)O(n)
C++ 代码
class Solution {
public:vector<double> dicesProbability(int n) {vector<double> res(n * 5 + 1);vector<vector<double>> f(n + 1, vector<double>(n * 6 + 1, 0));for (int i = 1; i <= 6; i ++)f[1][i] = 1.0 / 6;for (int i = 2; i <= n; i ++)for (int j = i; j <= i * 6; j ++)for (int k = 1; k <= 6; k ++){if (j - k >= i - 1)f[i][j] += f[i - 1][j - k]/6;}for (int i = 0; i <= n * 5; i ++)res[i] = f[n][n + i];return res;}
};