微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 60. n个骰子的点数

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

题目描述

把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;
    }
};

Java 代码

class Solution {
    public double[] dicesProbability(int n) {
        int[][] f = new int[n + 1][6 * n + 1];
        f[0][0] = 1;

        for (int i = 1; i <= n; i ++ ) {
            for (int j = i; j <= 6 * i; j ++ ) {
                for (int k = 1; k <= 6; k ++ ) {
                    if (k <= j) {
                        f[i][j] += f[i - 1][j - k];
                    }
                }
            }
        }

        double[] res = new double[6 * n - n + 1];
        double tot = Math.pow(6, n);
        for (int i = n; i <= 6 * n; i ++ ) {
            res[i - n] = f[n][i] / tot;
        }

        return res;
    }
}

Python 代码

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        f = [[0] * (6 * n + 1) for _ in range(n + 1)]
        f[0][0] = 1

        for i in range(1, n + 1):
            for j in range(i, 6 * i + 1):
                for k in range(1, 7):
                    if k <= j:
                        f[i][j] += f[i - 1][j - k]

        res = []
        tot = math.pow(6, n)
        for i in range(n, 6 * n + 1):
            res.append(f[n][i] / tot)

        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer