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

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

题目描述

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

image-20241107212341696

题意分析

同时掷 n 个普通六面骰子，每个骰子等概率地出 1 到 6 点。要交出的不是方案数，而是一个概率数组：把所有可能的点数和从小到大排好，第 i 个位置放的是「点数和取第 i 小的那个值」出现的概率，返回类型是浮点数组。这句话决定了答案的长度和下标含义，读题时必须先钉死，否则后面算得再对也对不上下标。

由此推出数组规格。n 个骰子每个最少 1 点，所以最小点数和是 n；每个最多 6 点，所以最大点数和是 6n；中间每个整数都可达，因为从任意一种凑法出发，只要把某个还没到 6 的骰子加一点，就能走到下一个和。于是可能的点数和共有 6n - n + 1 = 5n + 1 个，答案数组长度是 5n + 1 而不是 6n + 1，并且 ans[k] 对应的点数和是 k + n，反过来点数和 sum 应该写进 ans[sum - n]。这个偏移量是本题第一个坑。

约束是 1 <= n <= 11。上限小得很反常，正好透露两条信息。一是总的投掷结果数 $6^{11} = 362797056$ 不到 $4 \times 10^8$，普通浮点数装得下，不需要高精度或者取模。二是答案数组最长也只有 $5 \times 11 + 1 = 56$ 个位置，而投掷结果有三亿多种，说明海量结果会归并到同一个点数和上；换句话说信息在「点数和」这个维度上被压缩得极狠，按点数和聚合而不是按每一次具体投掷去枚举，才是这个数据范围在引导的方向。

还要注意各个点数和并不等概率。以两个骰子为例，和为 7 有 6 种凑法，和为 2 只有 1 种，所以绝不能偷懒返回 5n + 1 个相同的值。

边界情形有三处。n = 1 时答案是 6 个 $1/6$；两端的点数和 n 与 6n 概率恒为 $1 / 6^n$，可以拿来当第一道自检；所有元素之和必须等于 1，这是最好用的整体自检手段。判题按浮点误差比对，中间过程用整数计数、最后统一做一次除法，比一路带着小数走更稳。

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

核心思路

所有投掷序列等概率，因此先统计每个点数和的方案数，最后统一除以总方案数 $6^n$。

设当前已经处理若干个骰子，dp[s] 表示点数和为 s 的方案数。加入一个新骰子时，它可能掷出 1 到 6 点，所以旧状态 dp[s] 会分别贡献到 next[s + 1] 至 next[s + 6]。每种完整投掷序列都能按“前面骰子的点数和 + 最后一个骰子的点数”唯一分类，转移因此不重不漏。

第 k 轮只依赖第 k - 1 轮，用两个一维数组滚动即可。必须读旧数组、写新数组；若原地累加，本轮刚写入的状态会再次参与转移，相当于重复使用同一个骰子。

最终有效点数和是 n 到 6n，答案下标 i 对应点数和 n + i。

解题步骤

  • 初始化一个骰子：dp[1..6] = 1，总方案数为 6。
  • 从第 2 个骰子开始，创建全 0 的 next。
  • 枚举上一轮合法点数和，再枚举新骰子的 6 个点数，执行 next[sum + point] += dp[sum]。
  • 用 next 替换 dp，总方案数乘 6。
  • 将 dp[n..6n] 依次除以总方案数，写入长度为 5n + 1 的答案数组。

例如 n = 2 时，方案数依次为 1,2,3,4,5,6,5,4,3,2,1，总和为 36；两端概率都是 $1/36$，中间点数和 7 的概率是 $6/36$。

代码实现

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++) {
            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++ {
        ans[sum-n] = float64(dp[sum]) / float64(total)
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n^2)$。第 k 轮有 $5(k-1)+1$ 个有效点数和，每个状态固定枚举 6 个点数。
  • 空间复杂度：$O(n)$。两个滚动数组的长度均为 6n + 1。

关键点总结

  • 状态按“点数和”合并，避免枚举 $6^n$ 个投掷序列。
  • 转移按最后一个骰子的点数分类，天然保证不重不漏。
  • 计数阶段使用整数，最后只做一次概率除法。
  • 答案下标与点数和相差固定偏移 n。

易错点总结

  • 答案长度应为 5n + 1，不是 6n + 1。
  • 滚动更新必须读 dp、写 next，不能在同一数组上正向累加。
  • 总方案数是 $6^n$；少乘一次 6 会让概率总和变成 6。
  • 写答案时要用 ans[sum - n]，否则下标整体错位。
  • 方案数与总数应使用 64 位类型，避免扩展数据范围时溢出。

相似题目

题目 难度 考察点
1155. 掷骰子等于目标和的方法数 中等 同样的逐骰子递推，但骰子面数 k 可变、只问单个目标和且要求取模
1230. 抛掷硬币 中等 每次新增元素只有两个分支且概率不相等，必须在状态里直接累乘概率
377. 组合总和 Ⅳ 中等 可选数值由数组给定、每个数可无限次使用，转移退化成一维完全背包顺序