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

约 4 分钟
文章信息 13 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 剑指 Offer 剑指 Offer（第 2 版） 字节 阿里 拼多多 京东 快手 B站
标签
动态规划 数学 概率与统计

题目描述

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

image-20261001230752591

题意分析

将 n 个公平骰子各掷一次，返回点数和从 n 到 6n 的概率。等概率的是每个骰子点数确定的投掷序列，不是不同的点数和，因此先统计每个和对应多少种序列，再除以总序列数 $6^n$。

解法：滚动动态规划统计方案数

核心思路

[!blue]

处理完 i 个骰子后，dp[sum] 表示这 i 个骰子点数和为 sum 的投掷序列数。后续只关心已有的点数和，不关心此前各个骰子的具体点数，所以这些序列可以合并计数。

加入第 i + 1 个骰子时，它可能取 1..6 中的任一点数 point。每个旧序列都能接上这个点数，得到和为 sum + point 的新序列，因此执行 next[sum + point] += dp[sum]。反过来，任意新序列去掉最后一个骰子，就唯一对应一个旧序列和一个 point，所以转移不重不漏。

一个骰子的六个点数各有一种序列，作为初始状态。每轮创建全零的 next，只读取 dp，完成这一轮后再替换；同时把总序列数乘 6。最终将每个计数除以总数即可。

解题步骤

  • 令 dp[1..6] = 1，total = 6，表示已经处理一个骰子。
  • 加入第 dice 个骰子时，上一轮合法的和为 dice - 1 到 6 * (dice - 1)。
  • 对每个旧点数和枚举新骰子的六种点数，将计数累加到 next[sum + point]。
  • 用 next 替换 dp，并执行 total *= 6，直到处理完 n 个骰子。
  • 从小到大枚举 sum = n..6n，将概率写入 ans[sum - n]。当 n = 1 时没有转移，直接由初始状态得到答案。

代码实现

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

        for (int point = 1; point <= 6; point++) {
            dp[point] = 1;
        }

        long total = 6;

        for (int dice = 2; dice <= n; dice++) {
            // 新一轮从零开始，只读取上一轮，避免同一骰子重复参与。
            long[] next = new long[6 * n + 1];

            for (int sum = dice - 1; sum <= 6 * (dice - 1); sum++) {
                for (int point = 1; point <= 6; point++) {
                    next[sum + point] += dp[sum];
                }
            }

            dp = next;
            total *= 6;
        }

        double[] ans = new double[5 * n + 1];

        for (int sum = n; sum <= 6 * n; sum++) {
            // 点数和从 n 开始，写入下标要减去偏移，并先转浮点数。
            ans[sum - n] = (double) dp[sum] / total;
        }

        return ans;
    }
}

func dicesProbability(n int) []float64 {
    dp := make([]int64, 6*n+1)
    for point := 1; point <= 6; point++ {
        dp[point] = 1
    }

    total := int64(6)
    for dice := 2; dice <= n; dice++ {
        // 新一轮从零开始，只读取上一轮，避免同一骰子重复参与。
        next := make([]int64, 6*n+1)
        for sum := dice - 1; sum <= 6*(dice-1); sum++ {
            for point := 1; point <= 6; point++ {
                next[sum+point] += dp[sum]
            }
        }
        dp = next
        total *= 6
    }

    ans := make([]float64, 5*n+1)
    for sum := n; sum <= 6*n; sum++ {
        // 点数和从 n 开始，写入下标要减去偏移，并先转浮点数。
        ans[sum-n] = float64(dp[sum]) / float64(total)
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n^2)$。加入第 k 个骰子时，枚举 $5(k-1)+1$ 个旧点数和，每个状态固定转移 6 次；各轮长度累加为平方级。
  • 空间复杂度：$O(n)$。dp、next 和答案数组的长度都与 n 成正比，只保留相邻两轮状态。

关键点总结

[!green]

  • dp 保存序列数量，概率在最后统一计算。
  • 按最后一个骰子的点数分类，使所有投掷序列恰好被统计一次。
  • 第 i 轮只存在 i..6i 这些点数和，范围外的状态始终为零。
  • 点数和从 n 开始，答案下标则从零开始，两者相差 n。

易错点总结

[!yellow]

  • 答案长度是 6n - n + 1 = 5n + 1，不是 6n + 1。
  • 不能在同一数组上正向累加，否则本轮新产生的状态会继续转移，重复使用同一个骰子。
  • total 初始为 6，之后恰好乘 n - 1 次 6，最终才是 $6^n$。
  • 除法前必须转换为浮点数，否则整数除法会丢失概率的小数部分。本题 n 最大为 11，使用 long / int64 足以保存计数和总序列数。

相似题目

题目 难度 关联与区别
1155. 掷骰子等于目标和的方法数 中等 先统计各总点数的方案数，再除以6的n次方得到概率；原题只问给定目标点数的计数。
1230. 抛掷硬币 中等 同样逐次卷积概率状态，本题每个骰子有六个等概率结果，硬币只有两个且概率可不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/22511007
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！