企业官网建设流程全解析

1. 面试现场：这道题到底想考什么

作为一个刷了不知道多少遍剑指offer的过来人，我可以明确告诉你，第74题“n个骰子的点数”几乎是动态规划入门必刷的一题。它不刁钻、不偏门，但考察的恰恰是面试中最容易被问倒的几件事：状态定义合不合理、递推公式写不写得出来、空间能不能优化、边界处理细不细致。

先看题目要求：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s，输入n，打印出s的所有可能值出现的概率。比如n=1时，点数1到6每种出现的概率是1/6；n=2时，点数和从2到12，每种出现的次数不一样，概率也就不一样。

很多人第一反应是：这不就是枚举嘛。n个骰子每个6面，穷举所有组合，一共6^n种情况，算一下每种和出现的次数，再除以总数就完事了。这个思路本身没有问题，但如果你真的在面试里这么写，面试官大概率会追问一句“n等于10的时候你打算怎么跑？6的10次方是多少？”。一算，60466176，六千万量级，好像还能忍。那n等于100呢？6的100次方这个数，计算机算一辈子都枚举不完。

所以这道题的真正考点不是你会不会暴力，而是你知不知道暴力不可行的时候，该怎么用动态规划把重复计算砍掉。从暴力递归到记忆化搜索再到动规，这条路本身就是面试官想看到的思维过程。

再提醒一句，这道题在牛客网上的题目编号是JZ74，但在不同版本的书里题号可能不一样。有些同学在网上搜“剑指offer第74题”搜出来发现对不上，不要慌，看题目描述就行，关键词就是“n个骰子的点数”或者“打印骰子点数概率”。

2. 先说暴力方案：帮你理解为什么需要DP

2.1 暴力枚举的思路和实现

暴力方案不难。n个骰子，递归枚举每个骰子的点数，把所有组合的点数和记录下来，最后统计。用递归写大概是这个感觉：

def dices_probability_brute(n): if n <= 0: return [] # 点数和最小是n，最大是6n counts = [0] * (6 * n + 1) total = 0 def dfs(level, cur_sum): nonlocal total if level == n: counts[cur_sum] += 1 total += 1 return for i in range(1, 7): dfs(level + 1, cur_sum + i) dfs(0, 0) # 计算概率 res = [] for s in range(n, 6 * n + 1): res.append((s, counts[s] / total)) return res

代码本身确实不复杂，递归枚举每一种可能。问题在于复杂度——递归层数就是n，每层有6个分支，总的递归次数是6^n。n=3的时候是216次，完全没压力；n=8的时候是1679616次，开始有感觉了；n=12的时候大概是21亿次，基本跑不动了。

我第一次刷这题的时候，看到暴力解法觉得“没问题啊”，直到我试着跑了n=15，那真是等得花儿都谢了。所以你心里要有个数：暴力的复杂度是O(6^n)，空间复杂度O(6n)，这个复杂度在面试中是不能被接受的。

2.2 暴力方案的真正问题在哪

暴力方案的问题在于——大量的重复计算。举个例子，n=3的时候，递归路径(1,1,x)和(2,2,x)走到后面两层时，枚举的东西其实长得一模一样，都是“从当前和开始，继续投掷剩余骰子”。也就是说，只要“当前是第几个骰子”和“当前点数和”相同，往后的计算就是完全重复的。

这就像你从公司出门，不管你是坐地铁还是骑自行车到火车站，后面的高铁行程一模一样，没必要跑两遍。动态规划要干的事，就是把“后面的高铁行程”存下来，需要的时候直接查表。

有的同学喜欢用记忆化搜索来做这件事，本质上是把暴力递归的结果缓存起来。比如用字典存(key=level, cur_sum)对应的可能组合数，遇到一样的就直接返回。这个思路完全没问题，而且面试中如果你先讲暴力再讲“我发现有很多重复计算，所以加缓存”，面试官会非常认可。但是从代码简洁度来说，直接从底往上写DP会更干净利落。

3. 动态规划的核心：状态转移是怎么推出来的

3.1 状态定义与递推公式

动态规划的第一步永远是定义状态。这里的状态其实很好定义：dp[i][j]表示投掷前i个骰子，点数和为j的组合数（或者叫方案数）。注意，我们用组合数而不是概率，因为组合数是整数，算起来方便，最后统一除以总方案数6^n就能得到概率。

接下来是递推关系。投掷第i个骰子的时候，它的点数只可能是1到6，所以如果前i个骰子的和是j，那一定是前i-1个骰子的和是j-k（k从1到6）的情况下，第i个骰子掷出了k。写成公式就是：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + dp[i-1][j-4] + dp[i-1][j-5] + dp[i-1][j-6]

这个公式一定要理解透，它是整道题的灵魂。它的意思是：当前状态只能由上一层的六个状态转移过来。打个比方，如果你想知道“3个骰子掷出9”有多少种方式，你只需要看“2个骰子掷出8、7、6、5、4、3”这六种情况各有多少种方式，然后把它们加起来就行，因为第3个骰子掷出1、2、3、4、5、6分别对应这六种情况。

边界条件：dp[1][1]到dp[1][6]都是1，因为一个骰子掷出各点数只有一种方式，dp[1][0]和dp[1][7]这些不存在的和都是0。你也可以直接初始化i=0那层，令dp[0][0]=1，表示0个骰子掷出和为0有1种方式，这样递推起来更统一，代码也更简洁。

3.2 j的取值范围要仔细

这里有一个非常容易踩的坑：j的取值范围。前i个骰子的点数和，最小是i（全部掷出1），最大是6i（全部掷出6）。所以在三层循环里，j的循环范围应该写成range(i, 6*i+1)。

但是你要注意，在递推式dp[i][j] = sum(dp[i-1][j-k])里，dp[i-1][j-k]中的j-k可能落在边界外。比如j-6可能小于i-1，或者大于6*(i-1)，这种时候dp[i-1][j-k]等于0，不用管它。所以写代码的时候需要考虑下标是否合法，或者直接把dp数组每个元素初始化为0，然后j的循环范围取大一点，不存在的下标自然就是0。

我第一次写的时候，j的范围想偷懒直接写range(1, 6*n+1)，结果发现dp[i][j]里出现了一些“不可能是i个骰子掷出来”的和，但因为那些位置本来就是0，不影响后面计算，所以结果倒是正确的。不过更规范的做法还是把j的范围限制在[i, 6i]，这样逻辑清晰，也方便调试。

3.3 二维DP的代码实现

说了这么多，直接上代码。这是二维动态规划的标准写法：

def dices_probability_dp(n: int): if n <= 0: return [] # dp[i][j] 表示前i个骰子点数和为j的组合数 # j最大是6n，所以数组长度设为6n+1 dp = [[0] * (6 * n + 1) for _ in range(n + 1)] # 初始化：0个骰子，点数和为0的组合数是1 dp[0][0] = 1 # 逐层递推 for i in range(1, n + 1): # i个骰子 for j in range(i, 6 * i + 1): # 点数和范围 [i, 6i] # 第i个骰子掷出k（1~6） for k in range(1, 7): if j >= k: dp[i][j] += dp[i - 1][j - k] total = 6 ** n res = [] for s in range(n, 6 * n + 1): res.append((s, dp[n][s] / total)) return res

这个版本的时间复杂度是O(n * 6n * 6) = O(n^2)，准确地说循环次数大概是n * 6n * 6的级别。你可以算一下，n=100的时候，循环次数大概是1006006=360000，加加减减毫秒级完成，比暴力的6^100不知道快到哪里去了。这就是动态规划的价值。

4. 空间优化：从二维数组到一维数组

4.1 为什么能优化成一维数组

很多面试官在你写出二维DP之后，会接着问一句：能不能把空间复杂度从O(n * 6n)降到O(6n)？你如果答不上来，前面的功夫就白费了一半。

答案是能，而且思路很直观。观察递推式dp[i][j] = sum(dp[i-1][j-k])，你会发现第i层的每个状态只依赖第i-1层的六个状态，跟第i-2层、第i-3层没有任何关系。这就意味着我们不需要把前面所有层的值都存下来，只需要保留上一层的结果，滚动地算下一层就行。

这有点像爬楼梯：你只需要记住当前台阶和上一台阶，就能继续往上爬，不需要把走过的每一级台阶都拍张照片存起来。

4.2 滚动数组的实现细节与坑

一维优化的常见写法是：在循环每一层的时候，先用一个临时数组new_dp来存新结果，算完之后再赋值给dp数组。千万别在一个数组上原地更新，因为你更新dp[j]的时候，如果直接改原数组，后面计算dp[j+1]需要用到dp[j-k]（也就是还没更新过的旧值），结果就全错了。

正确写法有两种。第一种是用两个数组交替：

def dices_probability_optimized(n: int): if n <= 0: return [] # 只保留两层：pre和cur pre = [0] * (6 * n + 1) cur = [0] * (6 * n + 1) pre[0] = 1 for i in range(1, n + 1): # 当前层要重新初始化 for j in range(6 * n + 1): cur[j] = 0 for j in range(i, 6 * i + 1): total_count = 0 for k in range(1, 7): if j - k >= 0: total_count += pre[j - k] cur[j] = total_count pre, cur = cur, pre total = 6 ** n res = [] for s in range(n, 6 * n + 1): res.append((s, pre[s] / total)) return res

第二种更简洁的写法是，每一层直接在原数组上从后往前更新。为什么从后往前可以？因为dp[j]只依赖dp[j-k]，而j-k都比j小，如果你从大到小更新j，那么更新完dp[j]之后，后面用到的dp[j-k]（k>=1）都是更小的下标，而更小的下标恰恰还没被更新，所以它们仍然是上一层的值。这个技巧和背包问题里“倒序遍历数组压缩空间”是同一个道理。

我平时自己刷题喜欢用双数组的写法，逻辑更清晰，面试时说也容易解释。但如果你面试的是大厂，面试官可能更欣赏你能想到倒序更新这个trick——至少说明你背包问题的空间压缩已经形成肌肉记忆了。

5. 面试追问：骰子点数分布的性质

5.1 为什么中间概率高、两端概率低

这道题还有一个很容易被追问的知识点：为什么n个骰子的点数概率分布是对称的钟形曲线，中间和出现的概率最高，两端最低？

从递推公式也能看出一点端倪：dp[n][s]的值等于多个dp[n-1][s-k]的和，而dp[n-1]这一层本身就是中间大两边小，多个中间大的数字相加，新的中间值自然会更突出，两边递减更快。如果你画个柱状图或者折线图，会发现n越大，分布越向中间集中，形状越接近正态分布。

这个其实符合直觉。一个骰子的点数平均是3.5，n个骰子的期望和是3.5n。中间值离期望最近，组合方式最多，概率自然最高。比如2个骰子，和是7的情况有6种：(1,6)、(2,5)、(3,4)、(4,3)、(5,2)、(6,1)；而和是2的情况只有1种：(1,1)。这就是中间概率高的原因。

面试时如果面试官问到这，你可以顺便说一下期望值，展示你对概率论的理解：期望E = n * 3.5，分布围绕期望对称。不能说每个点的概率一样，那是均匀分布，不是这么回事。

5.2 变种题的应对思路

面试官很可能会给你变形题，最常见的有三种。

第一种，把“骰子”换成“硬币”。n个硬币，求正面朝上次数的概率分布。这个更简单，骰子的k范围从1~6变成0~1就行，递推公式变成dp[i][j] = dp[i-1][j] + dp[i-1][j-1]，本质上就是求组合数C(n, j)。

第二种，骰子点数不是1~6，而是任意指定的一组数字，比如{1, 2, 2, 3, 6}，这种有重复点数的骰子。处理办法是把内层循环的k从固定的1到6改成values数组的遍历，每个value代表一个面，其他逻辑完全不变。

第三种，求“点数和大于某个目标值的概率”。这个更简单，算出dp数组之后，把对应区间的概率累加就行，不需要额外写DP。

这三种变种我都会建议你在刷题时亲手写一遍，因为你永远猜不到面试官下一秒会怎么改条件。理解了状态转移的本质——“从哪些前置状态可以到达当前状态”——你就抓住了这类题的命脉，怎么变形都不怵。

6. 代码里面藏的细节：浮点数、边界、返回值

6.1 概率精度与返回格式

题目要求打印概率，这就涉及浮点数精度问题。在Python里直接做除法，默认是双精度浮点数，6^n可能是个非常大的整数，但除以之后还是能接受的精度。但是如果你在Java或C++里写，建议用double，避免用float，因为float的有效数字太少，n稍大一点误差就出来了。

题目没说返回格式的话，我个人习惯返回一个列表，每个元素是（点数, 概率）的二元组，或者两个平行数组：一个存点数，一个存概率。如果你不确定面试官要什么格式，直接问一句“希望我按什么格式输出”就行，这不算怯场，反而体现你考虑周全。

还有一点，概率的输出可能会要求保留特定小数位数。如果是OJ题，一定要仔细读题要求，保留几位小数、四舍五入还是截断，差一位都可能判错。如果是面试手写，直接说“我返回浮点数，你按需格式化”就行，一般不需要在这个环节纠结。

6.2 处理大n时的性能思考

如果n真的很大，比如100甚至1000，上面的O(n^2)算法其实已经很快了。但是要注意，要初始化一个(6n+1)长度的数组，每层循环的j范围是[i, 6i]，总的迭代次数是n * 6n * 6，也就是大约36n^2次加法操作。n=1000的时候，差不多3600万次操作，现代机器上也能一秒钟内跑完，完全够用。

但有个细节：n很大的时候，dp数组里的数值会非常大，中间的组合数可能是天文数字。Python的整数是任意精度的，所以不用担心溢出；但如果你用C++或Java，int会溢出，必须用long，再不够就得用大数类——这也是为什么一些OJ题里只要求输出概率而不是输出组合数的原因，因为概率虽然也是小数，但计算过程中用double可能会丢失精度，反过来很多题直接让你用double算概率数组而不是组合数数组，本质上是在规避大数问题。

如果遇到这种用double从头算概率的题目，递推公式就不是加组合数了，而是加权概率：dp[i][j] += dp[i-1][j-k] * (1/6)。这样每一步都在处理小数，数值不会爆，但会有累加误差，n大了之后误差不可忽视。所以我的建议是，组合数用Python算，概率最后一步再除，精度最好。

6.3 边界条件与异常输入

这段要单独拎出来说，因为很多同学栽在边界条件上。题目输入n是一个整数，如果n<=0怎么处理？不同题目要求不一样，有的是返回空数组，有的是抛出异常。保险的做法是开头先判断一下，n<=0就直接返回空列表。这个判断放在哪里都不影响主体逻辑，但是能防止你在n=0的时候算出来奇怪的东西。

还有一个容易被忽略的点：dp数组的下标从0开始，但点数和的最小值是n不是0。初始化dp[0][0]=1的意思是“掷0个骰子，和为0有1种方式”，这在递推时帮助我们从0层推到1层，非常优雅。但你要注意，循环j的时候如果从range(i, 6*i+1)开始，第一层i=1时j从1到6，能正确算出每个点数组合数是1；如果不是从1开始，比如从0开始，就会把“工个骰子掷出0”这种不存在的和也算进去，虽然结果可能不影响最后输出，但是逻辑上不严谨。

7. 其他思路：记忆化搜索、生成函数与数学理解

7.1 记忆化搜索的写法参考

如果你更习惯自顶向下的思考方式，记忆化搜索也是一个不错的选择。核心是递归函数f(i, j)表示前i个骰子和为j的组合数，用一个二维数组做缓存，递归枚举第i个骰子的6个面。

def dices_probability_memo(n: int): if n <= 0: return [] import functools @functools.lru_cache(None) def f(i, j): # 边界：0个骰子 if i == 0: return 1 if j == 0 else 0 # 剪枝：和超出可能范围 if j < i or j > 6 * i: return 0 total = 0 for k in range(1, 7): total += f(i - 1, j - k) return total total = 6 ** n res = [] for s in range(n, 6 * n + 1): res.append((s, f(n, s) / total)) return res

用lru_cache的好处是代码量少，不用手动管理缓存。坏处是递归深度在n较大时可能会触及Python默认的递归上限（大约1000层），所以你如果跑n=1000，这个写法会报递归栈溢出。解决办法是手动改sys.setrecursionlimit，但更稳妥的还是用自底向上的迭代DP，毕竟那个没有递归深度的顾虑。

7.2 生成函数：从数学角度理解

如果你对数学感兴趣，可以了解一下生成函数的方法。n个骰子的点数分布，本质上是多项式( x + x^2 + x^3 + x^4 + x^5 + x^6 )^n的系数展开。你看，每个骰子的点数可以写成x^1到x^6的加和，n个骰子就是6个多项式连乘，乘完之后每一项的系数就是对应点数和出现的组合数。

举个实际例子，n=2时就是(x + x^2 + ... + x^6)的平方，展开之后x^7的系数是6，正好对应“2个骰子和为7有6种组合”。这个方法在理论上很优美，也方便你推导更复杂的变种——如果骰子的面数不是6，就把多项式改成对应面数的形式。

不过在面试里，除非面试官是数学背景很深的人，一般不会要求你用生成函数解这道题。但如果你能熟练地提到这种视角，会是一个很好的加分项，因为它说明你不只会机械地套DP模板，而是看到了问题背后的数学结构。

7.3 时间复杂度对比速查

为了让你心里有数，我把几种方法的复杂度整理了一下：

这个表格不是死记硬背用的，而是让你理解：暴力一定不可取，DP复杂度是n的平方量级，在这个量级下n几千完全能跑。如果能顺手优化成O(6n)空间，那面试官对你的评价会更高。

8. 从刷题到面试：实战复盘与避坑清单

8.1 面试官问这道题时，他希望听到什么

这道题在面试中属于中规中矩的题型，不是难题，但如果你准备不足，很容易暴露出基本功问题。我复盘了身边同学被问这道题的经历，发现面试官最常关注的其实是三件事：你能否清晰解释状态定义、能否正确推导递推公式、能否主动优化空间复杂度。

很多同学上来直接写二维DP，写完就完事了，这其实没有把这道题的价值榨干。更好的思路是用口述的方式先把暴力方案提一下，然后说“我发现暴力解法存在大量重复子问题，所以考虑用动态规划，状态是…，转移是…，如果继续优化空间还能用滚动数组”，这样面试官能完整看到你的分析过程，而不是看你闷着头写代码。

另外提醒一点，面试时写完代码之后一定要自己手动跑一个简单用例，比如n=2，手动算出和是2到12的次数分别是1、2、3、4、5、6、5、4、3、2、1，然后看着代码推一遍确认输出正确。这个习惯非常值钱，因为面试官最不喜欢的就是“写完代码就喊完成，一跑就出错”的候选人。

8.2 我踩过的坑与避坑清单

我刷这题的时候掉进去过几个坑，写在这里给各位提个醒。

第一个坑是数组长度。如果你把dp数组的长度设为6n，而不是6n+1，那么下标最大值6n就访问越界了。写代码的时候默念“j的取值范围是到6n，所以数组长度至少是6n+1”。

第二个坑是内层循环的k。有的优化版代码里会把j-k<0的情况加进去，这其实不报错，因为dp[i-1][负数]在Python里会拿到列表末尾的值，结果完全错误且悄无声息。这个问题在Python里特别隐蔽，因为负数下标很“贴心地”不会越界报错。所以千万不要忽略if j >= k的判断，千万不要。

第三个坑是total的计算。总方案数是6^n，不是别的什么。我见过有人用sum(counts)去算总数，这当然也可以，但如果你的counts数组里混进了乱七八糟的0和异常值，sum的结果就会和真实总数不一样。直接用6**n最稳妥。

第四个坑是输出顺序。有些题要求按点数从小到大的顺序输出，有些要求按概率从大到小。读题的时候一定先看清楚再动手，别花十分钟写完了才发现输出顺序不对，那才是真的原地爆炸。

8.3 一道题衍生出的一类题

最后想分享一个我自己的体会：这道题学会之后，很多“总共有多少种方式”的题你都会觉得眼熟。比如“爬楼梯每次跨1或2阶，求n阶方式数”是它的退化版；“走棋盘从左上到右下每次只能向右或向下”是它的兄弟；“凑硬币有多少种组合方式”是它的亲戚。它们的共同模式都是：当前状态由之前某几个状态累加而来，关键在于正确划定哪些前置状态是合法的。

所以做完这道题之后，我建议你顺手把上面几种变种全刷一遍，刷完你会发现动态规划的状态转移思维会有质的飞跃。我当时就是这么干的，后来面试遇到“稍加变形”的DP题，心里基本不慌——因为我知道，核心永远是定义清楚状态，然后问自己一句话：什么状态能一步跳到我现在这个状态？

这道题说难不难，说简单也不简单，它像一个棱镜，折射出你对动态规划理解有多深。把它吃透，比囫囵吞枣刷十道题都管用。