题目描述

把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$

---

算法

(动态规划) $O(n^2)$

状态表示：f[i][j]，表示投 $i$ 次总和为 $j$ 的方案数
状态计算：按照第 $i$ 次投掷的点数为 $1，2，3，4，5，6$ 划分成六个集合
假设第 $i$ 次投掷的点数为 $k$，则状态转移方程为 $f[i][j] = f[i - 1][j - k]$，对于每种情况计算方案数，最后求和。

边界：

1. 初始值：$f[0][0] = 1$，由 $f[1][1] = 1$ 可以推出
2. 答案：$f[n][n]、f[n][2n]、…、f[n][6n]$，分别除以总方案数 $6^n$，最后就是每种和出现的概率值。

时间复杂度

状态数量有 $6n^2$ 个，状态转移时间为 $O(1)$，所以时间复杂度为 $O(n^2)$。
状态数量 * 状态转移所需时间 = $n^2 * O(1)$ = $O(n^2)$。

空间复杂度

$O(n^2)$

C++ 代码

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<int>> f(n + 1, vector<int>(6 * n + 1));
        f[0][0] = 1;

        for (int i = 1; i <= n; i ++ ) // 骰子个数
            for (int j = i * 1; j <= i * 6; j ++ ) // 第 i 个骰子投出后可能出现的总和
                for (int k = 1; k <= 6; k ++ ) // 按照 6 个点进行划分集合
                    if (k <= j)
                        f[i][j] += f[i - 1][j - k]; // 状态转移

        vector<double> res;           
        double tot = pow(6.0, n);
        for (int i = n; i <= 6 * n; i ++ ) res.push_back(f[n][i] / tot); // 求每种和的概率
        return res;
    }
};