CS-Notes 剑指 Offer 60n 个骰子的点数和概率分布——动态规划与滚动数组空间优化【免费下载链接】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 的每一个取值对应的概率返回结构为ListMap.EntryInteger, Doublekey 是点数和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 个骰子的点数 kk ∈ [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 ListMap.EntryInteger, 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); ListMap.EntryInteger, 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 个骰子最小点数为 ij i的状态恒为 0直接跳过减少无效计算计数用long类型以 int 计数的话n 较大时组合数会溢出见第 5 节最后统一换算概率概率 dp[n][i] / totalNum其中totalNum 6^n。注意原代码中dp[n][i]是long除以double的totalNum会自动完成浮点除法不会发生整除截断。2.3 复杂度时间状态数为(n1) × (6n1)每个状态枚举最多 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[n1][pointNum1]用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 ListMap.EntryInteger, 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); ListMap.EntryInteger, 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保持初值 1dp[1 - flag]即dp[0]——恰好是初始化时写入单骰子边界的那一层结果依然正确无需特判。3.3 复杂度时间O(6n²)与解法一相同多了一次 O(6n) 的清零不改变量级空间O(N)原文档标注的 O(N) 即long[2][6n1]的规模相比 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. 实现要点与常见坑计数溢出n 个骰子点数和的组合数增长极快dp计数必须用long原代码即如此。若用intn 稍大就会溢出为负数导致概率为负。整除截断概率换算必须保证浮点除法。dp[n][i] / totalNum中totalNum是doubleMath.pow(6, n)返回 double自动触发浮点除法若自行改用整型6^n计算总数则必须显式写dp[n][i] * 1.0 / totalNum。内层起点是 i 而不是 1j从ii 个骰子的最小和开始既正确又省掉了必然为 0 的状态同时k j的约束保证j - k 0不会越界访问负下标。滚动数组的清零与读取层不清零会混入 i-2 层的旧值结束时读取层是dp[1 - flag]而非dp[flag]这是滚动写法最常见的两处失分点。概率归一化验证所有点数和的概率之和应恰好等于 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考