剑指 Offer 60. n个骰子的点数

剑指 Offer 60. n个骰子的点数

难度：$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<=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=16​f(n−1,x−i)∗1/6
​

复杂度分析

• 时间复杂度：O(n2)O(n^2)O(n2)

• 空间复杂度 : $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;}
};