剑指60：n个骰子的点数

传送门

leetcode

题目描述

把 n 个骰子仍在地上，求点数和为 s 的概率。

C++ 代码 - leetcode

/*
    状态表示：
        dp[i][j] 表示投完 i 枚骰子后，点数 j 的出现次数。
    状态计算：
        for (第n枚骰子的点数 i = 1; i <= 6; i ++)
            dp[n][j] += dp[n - 1][j - i]

    空间复杂度：O(n^2)
*/
class Solution {
public:
    vector<double> statisticsProbability(int n) {
        int pointNum = 6;            // 一个骰子的点数
        int pointSum = pointNum * n; // n 个骰子的点数
        int f[n + 1][pointSum + 1];
        // base case
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= pointNum; i ++) {
            f[1][i] = 1;
        }
        for (int i = 2; i <= n; i ++) {
            for (int j = i; j <= pointSum; j ++) {
                for (int k = 1; k <= pointNum; k ++) {
                    if (j - k <= 0) {
                        break;
                    }
                    f[i][j] += f[i - 1][j - k];
                }
            }
        }

        int totalNum = pow(pointNum, n);
        vector<double> res;
        for (int i = n; i <= pointSum; i ++) {
            res.push_back(f[n][i] * 1.0 / totalNum);
        }
        return res;
    }
};

/*
    空间优化：一维
    空间复杂度：O(n)
*/
class Solution {
public:
    vector<double> statisticsProbability(int n) {
        int pointNum = 6;               // 一个骰子的点数
        int pointSum = pointNum * n; // n 个骰子的点数
        int f[pointSum + 1];
        // base case
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= pointNum; i ++) {
            f[i] = 1;
        }
        for (int i = 2; i <= n; i ++) {
            for (int j = pointNum * i; j >= i; j --) {
                f[j] = 0;
                for (int k = 1; k <= pointNum; k ++) {
                    if (j - k < i - 1) {
                        break;
                    }
                    f[j] += f[j - k];
                }
            }
        }

        int totalNum = pow(pointNum, n);
        vector<double> res;
        for (int i = n; i <= pointSum; i ++) {
            res.push_back(f[i] * 1.0 / totalNum);
        }
        return res;
    }
};

labuladong 题解

/*
	如果定义一个 dp(n, point) 函数表示 n 个骰子抛出 point 点数的概率，
	这个状态转移关系如下：dp(n, point) = sum{dp(n-1, point-k) where 1 <= k <= 6}

	自底向上的迭代解法
*/
class Solution {
public:
    vector<double> statisticsProbability(int n) {
        // n 个骰子可能扔出的结果的最大值和最小值
        int min = n, max = n * 6;
        // 定义：用 n 个骰子，凑出 point 的点数的概率是 dp[n][point]
        vector<vector<double>> dp(n + 1, vector<double>(max + 1));
        // base case：一个骰子扔出点数 1~6 的概率是 1/6
        for (int j = 1; j <= 6; j++) {
            dp[1][j] = 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 <= 0) {
                        break;
                    }
                    // i 个骰子扔出点数 j 的概率
                    // 可以通过 i - 1 个骰子认出点数 j - k 的概率推倒出来
                    dp[i][j] += dp[i - 1][j - k] * 1.0 / 6.0;
                }
            }
        }

        vector<double> res(max - min + 1);
        for (int i = 0; i < res.size(); i++) {
            res[i] = dp[n][min + i];
        }
        return res;
    }
};

/*
	自顶向下的递归解法
*/
class Solution {
public:
    vector<double> statisticsProbability(int n) {
        // n 个骰子可能扔出的结果的最大值和最小值
        int min = n, max = n * 6;
        memo = vector<vector<double>>(n + 1, vector<double>(max + 1, 0));

        vector<double> res(max - min + 1);
        for (int i = 0; i < res.size(); i++) {
            res[i] = dp(n, min + i);
        }
        return res;
    }

    // 定义：用 n 个骰子，抛出 point 点数的概率
    double dp(int n, int point) {
        // base case
        if (point <= 0) {
            return 0;
        }
        if (n == 1) {
            if (point > 6) {
                return 0;
            }
            return 1.0 / 6;
        }
        // 备忘录避免冗余计算
        if (memo[n][point] != 0) {
            return memo[n][point];
        }
        // 进行状态转移
        double prob = 0;
        for (int i = 1; i <= 6; i++) {
            prob += dp(n - 1, point - i) * 1.0 / 6;
        }
        // 结果存入备忘录
        memo[n][point] = prob;
        return prob;
    }

private:
    // 备忘录
    vector<vector<double>> memo;
};