企业官网建设流程全解析

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

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes

本篇是 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 降维"的通用技巧，本仓库同一分类的 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 题解 - 目录 中动态规划分类的其他题目共享同一套"定义状态 → 推导转移 → 降维省空间"的解题框架，建议结合该目录一并练习。

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes