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

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

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

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

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

当前位置: 算法 > 剑指offer > 剑指offer 60. n个骰子的点数
本文链接:https://www.mianshi.online/2804.html

题目描述

把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完整版