CS-Notes 剑指 Offer 60：n 个骰子的点数和概率分布——动态规划与滚动数组空间优化

本篇是 CS-Notes 剑指 Offer 题解（动态规划分类）中第 60 题的完整解析：把 n 个骰子扔在地上，求点数和为 s 的概率。读完本篇，你将掌握该题的状态定义与状态转移方程的推导、O(N²) 空间二维 DP 与 O(N) 空间滚动数组两种实现，以及概率换算、整数溢出与整除截断等实战坑点，能独立完成面试中"概率型 DP"类题目的建模与编码。

1. 题目与问题的数学结构

题目原文（见 notes/60. n 个骰子的点数.md）：

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

原题收录于 Lintcode 的 Dices Sum 问题（LeetCode 剑指 Offer 60 / LCOF 60 亦为同一题）。要求返回点数和从 n 到 6n 的每一个取值对应的概率，返回结构为 List<Map.Entry<Integer, Double>>：key 是点数和，value 是该点数和出现的概率。

在写代码之前，先明确几个决定状态空间的数学事实：

• 点数和的范围：每个骰子最小点数为 1、最大点数为 6，因此 n 个骰子的点数和最小为 n，最大为 6 * n，中间每个整数取值都可能出现，共 5n + 1 个合法点数和；
• 样本空间：n 个骰子共有 6^n 种等可能结果，因此点数和 s 的概率 = 「点数和为 s 的组合数」÷ 6^n；
• 分布形态：随着 n 增大，点数和的概率分布逐渐呈钟形，向期望值 3.5n 集中（面试中可补充说明这是中心极限定理的直观体现）。

所以解题的关键归结为：如何高效求出 n 个骰子点数和恰好为 j 的组合数 count(j)。这正是典型的二维递推问题。

2. 解法一：二维数组 DP（空间 O(N²)）

2.1 状态定义与转移方程

原文档给出的状态定义：使用二维数组 dp 存储点数出现的次数，dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

状态转移只需考虑第 i 个骰子的点数 k（k ∈ [1, 6]）：前 i 个骰子凑出点数 j，等价于前 i-1 个骰子凑出点数 j-k，再让第 i 个骰子掷出 k。于是：

dp[i][j] = Σ dp[i-1][j-k]   （k = 1..6，且 j-k >= 0）

边界条件：只有 1 个骰子时，点数 1~6 各出现一次，即 dp[1][1] = dp[1][2] = ... = dp[1][6] = 1。

2.2 完整代码（源自原笔记）

public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    final int face = 6;
    final int pointNum = face * n;
    long[][] dp = new long[n + 1][pointNum + 1];

    for (int i = 1; i <= face; i++)
        dp[1][i] = 1;

    for (int i = 2; i <= n; i++)
        for (int j = i; j <= pointNum; j++)     /* 使用 i 个骰子最小点数为 i */
            for (int k = 1; k <= face && k <= j; k++)
                dp[i][j] += dp[i - 1][j - k];

    final double totalNum = Math.pow(6, n);
    List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
    for (int i = n; i <= pointNum; i++)
        ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));

    return ret;
}

代码细节说明：

• pointNum = face * n 即最大点数和 6n，第二维开到 pointNum + 1，索引直接对应点数取值，不存在无用的稀疏空间；
• 内层 for (int j = i; ...) 从 i 开始而非 0，因为"用 i 个骰子最小点数为 i"，j < i 的状态恒为 0，直接跳过减少无效计算；
• 计数用 long 类型：以 int 计数的话，n 较大时组合数会溢出（见第 5 节）；
• 最后统一换算概率：概率 = dp[n][i] / totalNum，其中 totalNum = 6^n。注意原代码中 dp[n][i] 是 long，除以 double 的 totalNum 会自动完成浮点除法，不会发生整除截断。

2.3 复杂度

• 时间：状态数为 (n+1) × (6n+1)，每个状态枚举最多 6 个 k，即 O(6n²)；
• 空间：原文档标注为 O(N²)，即整个 dp 表的规模。

3. 解法二：滚动数组（空间 O(N)）

3.1 优化原理

观察转移方程 dp[i][j] 只依赖上一层 dp[i-1][*]，不依赖 dp[i-2][*] 及更早的层。因此只需保留相邻两层即可，用 long[2][pointNum + 1] 代替 long[n+1][pointNum+1]：

• 用 flag 作为"旋转标记"：第 i 层写在 dp[flag]，读取上一层 dp[1 - flag]；
• 每轮迭代开始时对 dp[flag] 整行清零，避免残留上一轮（该数组上一次被写入的是 i-2 层的数据）；
• i 从 2 到 n，每轮末尾 flag = 1 - flag 翻转指向。

循环结束后，最后一层数据落在 dp[1 - flag]（注意不是 dp[flag]——最后一次翻转后 flag 指向的是待清空的空层）。

3.2 完整代码（源自原笔记）

public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    final int face = 6;
    final int pointNum = face * n;
    long[][] dp = new long[2][pointNum + 1];

    for (int i = 1; i <= face; i++)
        dp[0][i] = 1;

    int flag = 1;                                     /* 旋转标记 */
    for (int i = 2; i <= n; i++, flag = 1 - flag) {
        for (int j = 0; j <= pointNum; j++)
            dp[flag][j] = 0;                          /* 旋转数组清零 */

        for (int j = i; j <= pointNum; j++)
            for (int k = 1; k <= face && k <= j; k++)
                dp[flag][j] += dp[1 - flag][j - k];
    }

    final double totalNum = Math.pow(6, n);
    List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
    for (int i = n; i <= pointNum; i++)
        ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));

    return ret;
}

一个值得注意的边界情况：n = 1 时外层 for 循环一次都不执行，flag 保持初值 1，dp[1 - flag] 即 dp[0]——恰好是初始化时写入单骰子边界的那一层，结果依然正确，无需特判。

3.3 复杂度

• 时间：O(6n²)，与解法一相同（多了一次 O(6n) 的清零，不改变量级）；
• 空间：O(N)，原文档标注的 O(N) 即 long[2][6n+1] 的规模，相比 O(N²) 显著下降。

4. 两种解法对比

维度	二维数组 DP	滚动数组 DP
状态	dp[i][j]：前 i 个骰子点数和为 j 的次数	同左，仅保留相邻两层
空间复杂度	O(N²)	O(N)
时间复杂度	O(6n²)	O(6n²)
额外操作	无	每轮对当前层整行清零，注意最终读取层为 dp[1 - flag]
适用场景	需要回溯每层中间结果、教学讲解	面试默认选择：空间最优且不易出错

滚动数组写法是"二维 DP 降维"的通用技巧，本仓库同一分类的 47. 礼物的最大价值 同样把按行递推的 DP 压缩成了一维数组；而 10.1 斐波那契数列、42. 连续子数组的最大和 等题则展示了滚动变量（把两层进一步压缩为两个变量）的极限形态。骰子这道题的滚动数组保留了"层"的结构，是最易理解的中间形态。

5. 实现要点与常见坑

1. 计数溢出：n 个骰子点数和的组合数增长极快，dp 计数必须用 long（原代码即如此）。若用 int，n 稍大就会溢出为负数，导致概率为负。
2. 整除截断：概率换算必须保证浮点除法。dp[n][i] / totalNum 中 totalNum 是 double（Math.pow(6, n) 返回 double），自动触发浮点除法；若自行改用整型 6^n 计算总数，则必须显式写 dp[n][i] * 1.0 / totalNum。
3. 内层起点是 i 而不是 1：j 从 i（i 个骰子的最小和）开始，既正确又省掉了必然为 0 的状态；同时 k <= j 的约束保证 j - k >= 0，不会越界访问负下标。
4. 滚动数组的清零与读取层：不清零会混入 i-2 层的旧值；结束时读取层是 dp[1 - flag] 而非 dp[flag]，这是滚动写法最常见的两处失分点。
5. 概率归一化验证：所有点数和的概率之和应恰好等于 1，可作为单测断言快速验证实现正确性。

6. 总结

"n 个骰子的点数"是概率型 DP 的代表题：状态 dp[i][j] = 前 i 个骰子点数和为 j 的次数，转移枚举最后一颗骰子的 6 种点数，最后用 dp[n][j] / 6^n 统一换算概率；实现上优先使用滚动数组把空间压到 O(N)。本题与 剑指 Offer 题解 - 目录 中动态规划分类的其他题目共享同一套"定义状态 → 推导转移 → 降维省空间"的解题框架，建议结合该目录一并练习。