企业官网建设流程全解析

这道“n个骰子的点数”在剑指offer系列里算是一道非常经典的动态规划题，很多同学第一次看到它都会觉得“这有什么难的，DFS枚举不就完了”，结果真上手一写才发现，n稍微大一点就卡死。更麻烦的是，就算你知道了要用DP，状态怎么定义、数组开多大、一维优化为什么要倒着更新，这些细节每一个都能让面试官追问到怀疑人生。这篇文章我会把从暴力递归到动态规划、再到滚动数组优化的完整过程都拆开讲，连带我实际刷题和面试中踩过的坑，希望帮正在准备算法面试的朋友把这道题彻底拿捏住。

先简单对齐一下题面：有n个骰子，每个骰子掷出1到6点的概率都是1/6，把所有骰子的点数相加得到一个总和s，输入n，要求输出每个可能点数和s出现的概率。点数和的范围很好算，最小是n个1相加得到n，最大是n个6相加得到6n，中间一共有5n+1个不同的取值。比如n=2时，s从2到12，概率分布是1/36、2/36、3/36、4/36、5/36、6/36、5/36、4/36、3/36、2/36、1/36，对称且中间最大。如果你刷过LeetCode的1155题“掷骰子的N种方法”，会发现它就是问凑到某个target的方案数，和这道题本质上是同一个问题，只是剑指offer这里要求输出概率，需要额外除以总方案数6^n。

为什么这道题值得反复刷？因为它把“穷举”和“递推”之间的分界线展示得很清楚。暴力思路几乎人人都有，但能不能在面试现场一步步把暴力优化成DP，这直接反映了对状态设计和重复子问题的理解深度。我在第一次遇到它时就吃了亏，所以整个思路演进的过程我会写得很细，包括当时是怎么想岔的，以及后来怎么一点点把岔路掰直的。

1. 先搞清楚题目问什么，以及为什么它值得刷

1.1 题面拆解

拿到这道题，第一件事不是写代码，而是跟面试官确认输出格式。剑指offer原书里的描述比较古早，说输入n，打印出点数和s出现的概率。但现在各家公司面试题的接口五花八门，有的要求返回double数组，下标从n开始对齐到6n；有的要求返回一个列表，每个元素是“点数和+概率”；还有的要求输出概率的分式形式。我自己的习惯是先问清楚“返回类型是什么，概率精度要求是什么”，这能省掉后续不少麻烦。

如果要求返回一个长度为5n+1的double数组，那么下标0对应s=n，下标5n对应s=6n，这个映射关系是第一个容易出错的地方。很多同学会把dp数组直接开成6n+1，然后用s本身做下标，这样也能算，但最后输出时要小心截断和越界。我记得有位同学第二次刷这题时，直接把下标s-n忘了减，导致输出数组开头多了一个0，后面所有的值整体往后错了一位，肉眼很难发现，但测试用例一跑就挂了。

再确认一下概率怎么算。如果统计出点数和s出现的方案数是cnt，那么总方案数是6^n，概率就是cnt除以6^n。之所以强调“方案数”，是因为这道题和纯概率题还不太一样，它底层是一个计数问题。理解了这一点，后面转移方程就很好想了。

1.2 为什么第一反应DFS会挂

我看到这题的第一反应就是递归：每颗骰子扔出1到6，扔完n颗后统计总和，最后把计数数组除以6^n。逻辑完全正确，但跑起来就完蛋。

假设n=11，6的11次方约等于3.6亿，就算每秒能处理几百万个状态，也要好几秒；n=20的时候，6的20次方是3.6万亿以上，这个数量级根本没有跑完的可能。递归不只是慢，还极其浪费空间，深度达到n时的调用栈开销也不小。更关键的是，DFS把大量子问题重复计算了无数次：前i颗骰子已经凑出某个和，后面的骰子怎么扔，和前面具体是哪种组合方式无关，但DFS仍然会把所有路径一条一条重新展开。

这个“前面的组合方式不影响后续结果”的特性，就是动态规划能优化的根源。我在学习时用了很久才理解这句话：DFS是按路径展开的，DP是按状态累积的。前者关注“每条路怎么走”，后者关注“走到每个状态的方案有多少”。这道题里骰子编号其实无关紧要，重要的是“已经扔了几颗”和“当前总和是多少”，所以状态就可以压缩成这两个维度，没有必要把每一颗骰子的点数都展开。

1.3 这道题的考察点

面试官喜欢这道题，是因为它有梯度，能分层考察人的水平。

最基础的一层是“能不能想到DP”，能想到就说明你不是只会背模板。中间一层是“能不能把转移方程写干净，并且正确初始化”，这考察对状态空间的理解。再往上一层是“能不能做空间优化”，从二维DP优化到一维滚动数组，这一步能刷掉很多人。最高一层是“能不能解释清楚为什么滚动数组要倒序更新”，如果这个问题能讲明白，面试官一般就会觉得你真的理解了。

另外，这道题也很适合考边界：n=1时只有6个值，n=0时怎么处理，数组越界怎么规避，6^n在n较大时会不会溢出。这些问题在实际面试中被追问的频率非常高。我甚至遇到过一位面试官直接说：“你先别写代码，告诉我你打算怎么测试这道题。”所以后面我专门把测试用例设计也整理了一节，这块内容平时刷题容易忽视，但面试里真的很加分。

2. 从暴力递归到动态规划的思路演进

2.1 暴力枚举的代价

先把暴力DFS的写法放出来，方便对照。伪代码如下：

void dfs(int diceLeft, int sum) { if (diceLeft == 0) { cnt[sum]++; return; } for (int face = 1; face <= 6; face++) { dfs(diceLeft - 1, sum + face); } }

这个写法在n很小的时候没有问题，但一旦n超过12，时间复杂度就是灾难级别的。复杂度是O(6^n)，空间复杂度是O(n)的递归栈。面试现场如果直接写这个，多半会收到一句“能不能优化一下”。

优化方向有两个。第一个是记忆化，把递归过程中的中间结果存下来。具体说，dfs(diceLeft, sum)表示“还剩diceLeft个骰子时，当前已经累计到sum”，可以在哈希表里记录每个状态的结果，避免重复计算。这种“自顶向下”的写法思路更贴近暴力枚举，码起来也快，但状态之间互相依赖的关系不容易看清楚，面试官如果追问“这个状态的结果是怎么组合出来的”，很多人会解释得比较乱。

第二种就是真正的DP，“自底向上”递推。既然从递归树能看到，剩余骰子数相同的状态，它们的子问题完全重叠，那不如直接从“扔了0个骰子”开始，逐轮往上累加。这样就把指数的复杂度压缩成了多项式复杂度。这里也顺带说明一个我踩过的坑：很多初学者在学DP时过分追求所谓“套路”，喜欢背模板，但这道题如果不知道状态是怎么设计出来的，遇到骰子面数变化的变形题还是会懵。

2.2 状态设计：骰子个数与点数和

动态规划的核心问题是定义状态。我习惯先把“当前做到哪一步”这个概念想清楚。可以这样理解：我们把n个骰子分成两段，前i个骰子已经考虑完了，后面还有n-i个骰子没考虑。当前关心的只是“前i个骰子点数和是多少”，至于这个和是哪些具体点数组合出来的，后面完全不在乎。

于是定义：

dp[i][s] 表示扔完前i个骰子后，点数和为s的方案数。

这里用“方案数”是有讲究的。如果直接用概率定义状态，比如dp[i][s]表示“前i个骰子点数和为s的概率”，转移时每一轮都要除以6，浮点误差会一层层累积，而方案数全是整数，最后再统一除以6^n，误差会小得多。对于面试题来说，先算方案数再转概率是最稳妥的路线。

现在观察状态空间的范围。扔完i个骰子，最小和是i，最大和是6i，所以理论上dp[i]只需要一个长度为6i+1的数组就够了。但我们写代码时通常开一个二维数组dp[n+1][6n+1]，把每一轮所有的合法区间都塞进去，取数方便，也不用担心越界。这里有个细节，dp[0][0]要等于1，表示“扔完0个骰子，和是0的方案数为1”，它是整个递推的起点。

2.3 转移方程是怎么推出来的

转移方程要从“最后一颗骰子”的角度去推。假设已经扔完了前i-1个骰子，累计和是x，现在第i个骰子扔出了k点，那么新的和就是x+k。反过来，我们要让前i个骰子的和变成s，只需要让前i-1个骰子的和是s-1、s-2、…、s-6，分别对应第i颗骰子扔出1到6点。

所以转移方程是：

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

其中所有下标都要保证非负。这个方程非常像一维背包里的“组合版”，区别在于每个骰子必须取一个面，而且面数固定为6。

光看公式可能还是有点抽象，我举个例子。n=2，也就是两个骰子，我们要算s=4的方案数。用上面的公式：

dp[2][4] = dp[1][3] + dp[1][2] + dp[1][1]

因为一个骰子时，点数和为1、2、3的方案数都是1，所以结果等于3，对应的是(1,3)、(2,2)、(3,1)这三种真实组合。这个推导过程非常重要，因为它不仅验证了公式，还解释了为什么是加法：第i个骰子扔出的点数互相独立、互不重叠，所以前i-1个骰子所有能到达s-k的方案，都能加上第i个骰子的k点成为合法方案，直接相加即可。

写代码时，循环的顺序也值得注意。外层循环当然是骰子数i从1到n，内层循环是当前点数和s从i到6i。s的下界为什么是i而不是0？因为i个骰子最小和就是i，小于i的dp[i][s]必然是0，没必要遍历。内层还有一个k循环，枚举1到6。这样三层循环整体的时间复杂度是O(n * 6n * 6)，也就是O(n^2)，空间复杂度是O(n * 6n)，也就是O(n^2)。这个复杂度对于常规n已经足够好。

3. 代码实现：二维DP、滚动数组、概率型DP

3.1 最直观的二维DP

直接按照转移方程写，逻辑最清晰，也最适合面试时先给出来。我用C++写一版：

vector<double> diceProbability(int n) { vector<vector<long long>> dp(n + 1, vector<long long>(6 * n + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int s = i; s <= 6 * i; s++) { long long total = 0; for (int k = 1; k <= 6; k++) { if (s - k >= 0) { total += dp[i - 1][s - k]; } } dp[i][s] = total; } } double all = pow(6, n); vector<double> res(5 * n + 1); for (int s = n; s <= 6 * n; s++) { res[s - n] = dp[n][s] / all; } return res; }

几个容易出错的地方我单独标一下。数组大小是n + 1行、6 * n + 1列，第0行第0列是初始边界，这个很多人写二维DP时容易漏。内层k循环里判断s - k >= 0其实是因为我们只开了6n+1列，下标不能变负，实际有效的上一个状态还要满足s - k落在[i - 1, 6 * (i - 1)]区间，但额外加判断会让代码变丑，而且数组初始为0，用s-k>=0再配合外层s >= i已经足够排除大部分非法情况。

如果对空间要求不敏感，二维版本已经能被面试官接受了。我建议大家在纸上把dp表手动推导一遍n=2的情况，整个过程跑完后，你会发现最后一行的非零值恰好落在[2,12]区间，这就是后面概率数组取值的来源。手动推一遍还有一个好处，就是面试官让你解释时你能说得头头是道。

3.2 一维滚动数组优化

空间复杂度能不能压到O(6n)？当然能。因为dp[i][s]只依赖于dp[i-1][...]，跟更早的状态没有任何关系，所以我们只需要保存“上一轮”的值和“当前轮”的值。最稳妥的写法是用两个数组交替：

vector<double> diceProbability(int n) { vector<long long> pre(6 * n + 1, 0), cur(6 * n + 1, 0); for (int s = 1; s <= 6; s++) pre[s] = 1; for (int i = 2; i <= n; i++) { fill(cur.begin(), cur.end(), 0); for (int s = i; s <= 6 * i; s++) { long long total = 0; for (int k = 1; k <= 6; k++) { if (s - k >= i - 1) { total += pre[s - k]; } } cur[s] = total; } swap(pre, cur); } double all = pow(6, n); vector<double> res(5 * n + 1); for (int s = n; s <= 6 * n; s++) { res[s - n] = pre[s] / all; } return res; }

注意这里我已经把pre初始化为第一个骰子的结果，也就是只有s=1到6时为1。然后从第二个骰子开始迭代，判断s - k >= i - 1是为了保证取到的下标落在上一轮的有效范围内。

但面试官往往会追问：“能不能只用一个数组？”这时候就涉及滚动数组的倒序更新了。只用一个数组的写法如下：

vector<double> diceProbability(int n) { vector<long long> dp(6 * n + 1, 0); for (int s = 1; s <= 6; s++) dp[s] = 1; for (int i = 2; i <= n; i++) { for (int s = 6 * i; s >= i; s--) { long long total = 0; for (int k = 1; k <= 6; k++) { if (s - k >= i - 1) { total += dp[s - k]; } } dp[s] = total; } } // 后面取概率的代码同上 }

为什么s要从大到小遍历？因为计算dp[s]时需要读取dp[s-k]，而s-k一定小于s。如果s从小到大遍历，计算dp[s]时，dp[s-k]很可能已经被这一轮更新成了“当前i个骰子的结果”，但我们要用的其实是“上一轮i-1个骰子的结果”。一旦读错，就相当于把第i个骰子重复使用了多次，方案数会严重膨胀。反过来，从大到小更新，由于s-k小于s，而s-k对应的下标还没有被本轮循环处理过，读到的就一定是上一轮的旧值，逻辑就对了。

这个“倒序”的坑几乎每个刷背包问题的人都踩过。我强烈建议拿到代码后做这么一件事：手动模拟n=3、s=4的情况，分别用正序和倒序算一遍，看结果差多少。相信我，算过一次之后，你对倒序的理解会非常深刻。

3.3 另一种思路：直接算概率

有时候n比较大，比如面试官说n可以到100甚至200，这时6^n早就超过double能精确表示的整数范围了，再用pow(6,n)去归一化，精度堪忧。但其实也没必要先算方案数再除，我们可以把概率直接作为状态值来维护。

定义：

dp[i][s] 表示前i个骰子点数和为s的概率。

转移时，第i个骰子扔出k点的概率是1/6，所以：

dp[i][s] += dp[i-1][s-k] * (1.0 / 6.0)

初始化时，第一个骰子每个点数的概率都是1/6。最后dp[n]中从n到6n的概率直接就是我们需要的答案，不用再除以总方案数。这个写法的好处是彻底绕开了6^n的溢出问题，坏处是浮点运算变多，误差会累积。好在本题涉及的浮点误差非常小，常规n范围内完全够用。

我个人建议把方案数版和概率版都会写。面试先给方案数版，解释“为什么要用long long做计数”，然后主动提一句“如果n特别大，我会换概率型DP避免总方案数溢出”，这一下就能展现出你对数值敏感度的掌控，比被动等面试官问要强很多。

4. 面试官爱追问的延伸问题

4.1 骰子面数不是6怎么办

这是最常见的变形：如果每个骰子不是6面，而是m面，点数从1到m，怎么办？其实转移方程只需要把k的枚举范围从1到6改成1到m，状态的上下界从n和6n改成n和m*n。代码里的循环条件对应改一下即可。

复杂度也会跟着变：O(n * m * n * m)? 其实准确说是O(n * (mn) * m) = O(n^2 * m^2)。如果m很大，可以考虑用前缀和优化。具体来说，dp[i][s]是dp[i-1][s-m]到dp[i-1][s-1]这一段的和，因为转移区间连续，所以可以维护一个滑动窗口，让内层循环从O(m)变成O(1)。这种优化思路和滑动窗口、前缀和相关的题目很像，面试官往往会很喜欢听。

有一个容易忽略的细节，就是初始化。骰子面数变成m后，第一轮dp[1][1]到dp[1][m]都为1，有效区间不再是1到6，写错了后面全错。我当时第一次写m面骰子时，就因为在初始化里把6写成了硬编码，导致m=8时前两个值正确、后面的概率全变成0，排查了好久才发现是初始化的问题。所以写通用版本时，尽量不要在核心逻辑里出现魔法数字6，宁可多传一个参数m。

4.2 只问某个点数和出现的概率

有时候题目改成“只求点数和为target的概率”。这时仍然可以用完整DP，但要算出整个表，最后取dp[n][target]，时间复杂度还是O(n^2)。其实可以剪枝：因为target是固定的，每一轮里超过target的状态完全不用维护，所以dp数组可以只开到target+1，同时每一轮的和s只枚举到min(6i, target)。

另一个更紧凑的思路是使用递归+备忘录，或者直接用一维DP压缩空间。如果target很小，比如n=10、target=12，你会发现绝大部分状态都不需要算，这种局部化能力也是面试中容易被考到的。不过需要提醒的是，如果target不是特别小，这种优化带来的收益有限，不要为了炫技把代码变得很难读。

4.3 和生成函数、正态分布的关系

理解这题再深一层，就能看到它的数学背景。每个骰子的点数分布可以用多项式表示，一枚骰子对应(x + x^2 + ... + x^6)/6，n个骰子点数和s的概率就是上面这个多项式的n次幂中x^s的系数。这就是生成函数或者多项式卷积的视角。如果你会FFT，甚至可以在O(n log n)的时间复杂度内算出n较大时的分布，不过面试里一般不指望你用FFT，但提一嘴能体现知识广度。

当n越来越大时，点数和s分布的标准化形态会越来越接近正态分布。期望是3.5n，方差是35n/12，标准差约等于sqrt(35n/12)。所以点数和大概率落在3.5n加减两个标准差范围内。这也是“中间概率最大，两边逐渐递减”的理论来源。面试官如果问“为什么中间值出现概率最大”，你可以从组合数最多来解释：中间值对应的拆分方式最多。如果还能补一句“大n的极限是正态分布”，基本就是这一问的加分答案了。

5. 常见错误与现场排查实录

5.1 下标错位问题

这是错误率最高的一类。很多同学在最后组装答案时，直接用s当数组下标，但题目要求的返回数组下标0对应s=n，不对齐就会错位。错误的表现往往是：第一个输出是0，或者最后一个值被截断。排查方法很简单，先把dp[n]这一行的非零区间打印出来，再从n到6n把它硬拷贝到结果数组里，始终记得返回数组的长度是5n+1而不是6n+1。

还有一个下标相关的坑，就是转移方程中dp[i-1][s-k]的s-k可能会落到上一轮合法区间之外。如果数组开得够大，读到的就是0，不会影响结果；如果数组开得刚好，可能越界。所以无论怎么写，都要确保数组列数至少是6n+1，并且下标不小于0。我在自己实现时习惯多开一列，用大小6 * n + 1而不是6 * n，就是为了省去反复思考边界的心智成本。

5.2 一维更新顺序踩坑

滚动数组的倒序更新问题，前面已经讲得比较细了，我再补一个具体的错误现象。如果采用正序更新，n=2时计算结果很可能变成：和为2的概率是1/36、和为3的概率是2/36、和为4的概率是5/36？总之就是比正确值大。原因就是本轮新值被反复当作上一轮旧值使用，导致状态被重复累加。

排查技巧是拿小规模结果做对照。n=2时正确概率分布是完全确定的，概率和应为1，且满足对称性。如果算出来不对称，基本就是更新顺序或初始化错了。用对称性来检测是很快的：n固定时，dp[n][s]应当等于dp[n][6n - s]，也就是和s与和6n-s的方案数相等。这个性质在调试时非常好用，只要发现不对称，立刻知道某个环节出了问题。

5.3 精度与溢出

方案数可能非常大。n=20时，6^n约等于3.6e15，已经逼近long long的上限9.2e18，再往上就危险了。如果是用long long计数，建议先和面试官确认n的范围；如果n可能超过30，long long一定不够，这时要么用概率型DP，要么对总方案数做log处理。pow函数返回的是double，虽然不溢出，但n很大时继续做除法得到的小概率，精度也需要注意。

还有一个我实测过的细节：不要用float。很多语言里float只有大约7位有效数字，而double有15位左右。这道题的概率动辄1/6^n，数值很小，float会把后面几位全抹掉，导致几个相邻概率看起来完全相同，输出格式巨丑。面试中如果要求打印概率到小数点后几位，float基本必挂。

5.4 测试用例怎么设计

我会把这题的测试用例归成四类。第一类是边界小值：n=1，输出是6个1/6，这是最简单的验证点。第二类是常规小值：n=2，输出对称，中间概率最大，精确值可以用手算枚举对比。第三类是递归和DP一致性：n=4或n=5时，先跑一遍DFS暴力结果，再跑DP结果，两个数组对比，如果完全一致说明转移方程没错。第四类是压力测试：n=30甚至n=100，重点看不超时、不溢出、概率和约等于1。

概率和约等于1这个检查点很关键。不管n多大，所有可能概率加在一起必须等于1（由于浮点误差通常是非常接近1，比如0.999999或1.000001）。如果概率和偏离1很多，一定有问题。我在调试过程中多次靠这个小技巧快速定位到“是不是整除没写对”或“是不是有状态没加进去”。

最后再分享一点个人体会

这道题我前前后后刷了至少五六遍，每次都有新的收获。第一遍学会二维DP，第二遍搞懂滚动数组，第三遍才真正理解倒序更新的本质，到后来看生成函数视角又觉得整个分布只是一个多项式展开。现在我带同学准备面试时，最喜欢让他们做的一件事就是：把问题从数值改成“打印概率分布”，再改成“只求某个和的概率”，再改成“m面骰子”，甚至改成“每个骰子点数范围不同，比如第i个骰子是i+1面”。每一次变形都在逼迫大脑脱离背模板的舒适区。

如果你正在准备算法面试，我的建议是不要只满足于把代码写对。找一张纸，手动推导n=3时dp数组从第一轮到第三轮的完整变化，然后再对照代码走一遍，你会发现自己对状态空间的理解立刻提升一个档次。等到面试官问你“为什么要倒序更新”时，你只需要在纸上写两行正序的计算过程，他就能看出你真的懂了。这道题从来不是考你会不会背，而是考你懂不懂“状态是如何流动的”。