企业官网建设流程全解析

1. 题目到底在问什么：一个让无数人栽跟头的“简单”概率题

先说说我自己的经历。第一次在LeetCode上看到1227这道题时，我以为是道送分题：飞机座位分配，这不就是个排列组合吗？结果动手一写，才发现完全不是那么回事。题目描述很简短，但里面藏着一个特别反直觉的概率结论——第n个乘客坐在自己座位上的概率，居然恒等于1/2，跟n有多大没关系。很多人在评论区吵翻了天，有人用蒙特卡洛模拟验证，有人推公式推到怀疑人生，还有人说这题应该归为“脑筋急转弯”而不是“动态规划”。但我觉得，这道题恰恰是理解“概率转移”和“状态压缩”的绝佳素材，比很多hard题都值得仔细咀嚼。

先看题目原意：一架飞机有n个座位，编号1到n。第1个乘客找不到自己的登机牌（或者干脆丢了），于是他随机选一个座位坐下。后面的乘客按顺序登机：如果自己的座位还空着，就坐自己的座位；如果自己的座位被占了，就随机在剩余空座里挑一个。问：第n个乘客（也就是最后一个乘客）恰好坐在自己座位上的概率是多少？

注意几个关键约束：第1个乘客是随机乱坐的，这一点是整个问题的“原罪”。后面的乘客都是“理性”的，只有在座位被占时才随机乱选。最后一个乘客没有任何选择余地，他只能坐剩下的那个座位——所以问题等价于“最后一个剩下的座位，恰好是第n个乘客自己的座位的概率”。

这道题之所以经典，是因为它表面上看起来像一个递推概率问题，但实际上可以用极其简洁的数学归纳法解决。更妙的是，答案与n无关，永远是1/2（n=1时除外，概率为1）。我第一次算出这个结果时还不敢相信，特意写了模拟程序跑了十万次，才心服口服。

这篇文章我会从直觉到证明，从模拟到代码，把这道题彻底拆开。无论你是准备面试、刷周赛，还是单纯对概率题感兴趣，相信都能从中收获一些“原来如此”的瞬间。

2. 从暴力模拟到本质理解：先跑一遍，再谈公式

2.1 为什么先做蒙特卡洛模拟

看到概率题，很多人的第一反应是推公式。但我个人的习惯是先写一个暴力模拟，把结果跑出来，再回头想为什么。因为模拟能给你一个“答案的直觉锚点”，免得后面推导时方向跑偏。这道题尤其适合模拟：状态空间简单，逻辑直接，写起来也就几十行。

模拟的思路非常直白：

• 初始化一个长度为n的布尔数组，表示每个座位是否被占。
• 第1个乘客随机选一个座位坐下。
• 从第2个乘客到第n个乘客依次登机：
  • 如果自己的座位空着，就坐自己的座位。
  • 否则，从剩余空座中随机选一个。
• 最后检查第n个乘客是否坐在自己的座位上。

重复这个实验m次，统计成功的次数除以m，就是概率的估计值。

我之前用Python写过一版，核心逻辑长这样：

import random def simulate_once(n): seats = [False] * n # 座位编号 0..n-1，乘客编号 0..n-1 # 第1个乘客（编号0）随机坐 first_seat = random.randint(0, n - 1) seats[first_seat] = True for passenger in range(1, n): if not seats[passenger]: # 自己的座位空着，直接坐 seats[passenger] = True else: # 自己的座位被占了，从空座里随机选 empty = [i for i in range(n) if not seats[i]] chosen = random.choice(empty) seats[chosen] = True return seats[n - 1] # 最后一个乘客是否坐在自己的座位上 def simulate(n, trials=100000): ok = 0 for _ in range(trials): if simulate_once(n): ok += 1 return ok / trials for n in [2, 3, 5, 10, 100]: print(f"n={n}, probability={simulate(n):.4f}")

跑出来的结果大概是这样：

看到没，不管n是3还是100，概率都稳定在0.5附近。这个结果本身就很有意思——如果这题的结果随n变化，比如1/n或者1/n!，那模拟也会给出对应的趋势。但稳定在1/2，说明背后一定有一个非常简洁的对称性或者不变性在起作用。

2.2 模拟代码的复杂度问题

上面的模拟代码虽然正确，但效率很低。每次随机选空座都扫描整个数组，复杂度O(n^2)，n=100时还好，n=10000就非常慢了。如果只是验证结论，可以接受；但如果你想用模拟来“证明”答案，那在效率上就有点说不过去。

优化方法也很简单：用集合维护空座索引，或者用Fisher-Yates洗牌的思想来模拟。其实更优雅的方式是：不需要记录每个乘客具体坐哪，只需要维护“哪些座位被异常占据”就行了。但这里我们不纠结模拟性能，重点在于通过模拟得出“概率恒定”的猜想，然后去证明它。

提示：模拟不是数学证明，只能提供经验支持。你用100万次模拟得到的0.5001，依然不能替代严格的推导。但模拟能帮你快速发现问题、检验公式，性价比极高。

3. 数学推导：三种解法，从递归到归纳

3.1 递归视角：把问题缩小

这道题最经典的解法是递归。设 f(n) 表示“一共有n个乘客时，最后一个乘客坐在自己座位上的概率”。注意，这里的“n个乘客”对应题目的完整场景，而不是某种子问题。我们尝试把第1个乘客的行为分情况讨论。

第1个乘客随机选一个座位，有n种等可能的选择。他选到自己的座位（概率1/n）的话，后续所有乘客都会坐自己的座位，第n个乘客当然坐在自己座位上。他选到第n个乘客的座位（概率1/n）的话，第n个乘客的座位没了，最后他肯定坐不到自己的座位（因为最后一个剩下的空座就是第1个乘客自己的座位，或者某个中间乘客的座位，总之不是第n个座位）。他选到第k个乘客的座位（2 ≤ k ≤ n-1，每个概率1/n）的话，会发生什么？

当第k个乘客登机时，他发现自己的座位被占了，于是会随机从剩余空座里选一个。这时，前k-1个乘客（除第1个外）都已经坐在自己的座位上了，剩余的空座是：第1个乘客的座位、第k+1到第n个乘客的座位，以及……等等，还需要把第k个乘客随机选座后的情况继续推演下去。

这里如果直接展开，会陷入一个“乘客不断被挤走”的链条。但我们可以做一个关键的等价变换：当第k个乘客被迫随机选座时，他面对的局面，其实和“一个新的问题”非常像——只不过这个新问题里，第k个乘客扮演了当初第1个乘客的角色，而“第n个乘客的座位”依然是那个需要保住的座位。

具体来说，当第k个乘客随机选座时，剩余空座的集合是：第1个乘客的座位、第k+1个座位、……、第n个座位（共n-k+1个空座）。如果第k个乘客恰好选择了第k+1个座位，那么第k+1个乘客登机时也会面临同样的困境，继续随机选。依此类推，直到某个乘客选到第1个乘客的座位，或者选到第n个乘客的座位，链条才结束。

这个链条有一个非常重要的性质：在链条结束之前，所有被“挤”的乘客都是按顺序的，而且每次随机选择都是在“第1个乘客的座位”和“第n个乘客的座位”之间做某种“等价赌博”。最终决定第n个乘客命运的，并不是中间那些“过渡乘客”选了哪个座位，而是“第一个在集合{第1个乘客的座位，第n个乘客的座位}中被选中的座位”到底是哪一个。

因为这两个座位在每次随机选择中都是等概率的（它们始终同时出现在剩余空座中，直到其中一个被选中），所以第n个乘客的座位先被选中的概率，等于第1个乘客的座位先被选中的概率，也就是1/2。无论n多大，这个对称性都成立。

上面的叙述虽然直观，但对初学者来说可能有点绕。我再用递归式表达一下：

设 f(n) 为原问题的答案。第1个乘客选座位后，分三种情况：

• 选自己的座位：概率1/n，之后一切都好，最后一个乘客必坐自己座位，贡献 1/n × 1。
• 选第n个乘客的座位：概率1/n，最后一个乘客必无座，贡献 1/n × 0。
• 选第k个乘客的座位（2 ≤ k ≤ n-1）：概率1/n。此时相当于把问题“降级”为：从第k个乘客开始，剩余空座数为 n-k+1，且有一个“占座者”（第1个乘客）的座位是特殊的。最后一个乘客能坐到自己座位的概率等价于 f(n-k+1)……吗？

这里要小心。直接写成 f(n-k+1) 其实不太严谨，因为子问题的“第一个乱坐的人”可能不是第k个乘客本人，而是第1个乘客。但我们可以把视角切换一下：当第k个乘客登机时，他发现自己座位被占，要随机选座。如果把第k个乘客看作“新的乱坐者”，那么他面对的剩余空座集合是 {第1个乘客的座位, 第k+1个座位, ..., 第n个座位}。这个集合里有 n-k+1 个座位，其中“第n个乘客的座位”就是需要保住的座位。这和原始问题（n-k+1个乘客，第一个乘客乱坐）的结构完全一致——都是“第一个乱坐的人随意选一个座位，后续按规则坐”。所以子问题的概率确实等于 f(n-k+1)。

于是递推式：

f(n) = 1/n × 1 + 1/n × 0 + (1/n) × Σ_{k=2}^{n-1} f(n-k+1)

令 m = n-k+1，当 k 从 2 到 n-1 时，m 从 n-1 到 2。所以：

f(n) = 1/n + (1/n) × Σ_{m=2}^{n-1} f(m)

接下来就是数学归纳法的舞台。

3.2 归纳证明：三步走

我们用归纳法证明：对所有 n ≥ 2，f(n) = 1/2。

基例：n = 2 时，第1个乘客随机选座位，选到自己座位的概率 1/2，此时第2个乘客坐自己座位；选到第2个座位概率 1/2，此时第2个乘客坐不到自己座位。所以 f(2) = 1/2。成立。

归纳假设：假设对所有 2 ≤ m ≤ n-1，都有 f(m) = 1/2。

归纳步骤：对 n，利用上面的递推式：

f(n) = 1/n + (1/n) × Σ_{m=2}^{n-1} f(m) = 1/n + (1/n) × Σ_{m=2}^{n-1} (1/2) = 1/n + (1/n) × (n-2)/2 = 1/n + (n-2)/(2n) = (2 + n - 2) / (2n) = n / (2n) = 1/2

证毕。这个证明极其简洁，核心就在于递推式里 Σ f(m) 的和刚好被 1/n 这个系数“消化”掉了。如果 f(m) 不是 1/2，这个递推式求解就会复杂很多。所以 1/2 这个答案不是“碰巧”，而是递推结构内禀的稳定点。

3.3 更直观的“三乘客”特例分析

为了让大家彻底理解，我拿 n=3 手算一遍。3个乘客、3个座位。第1个乘客随机选：

• 选1号座（自己的）：概率1/3。后面第2、3乘客都坐自己座位，第3乘客坐自己座，成功。
• 选2号座：概率1/3。第2个乘客登机发现2号座被占，只能在1号和3号座位中随机选。
  • 选1号座：概率1/2，此时第3乘客只能坐3号座，成功。
  • 选3号座：概率1/2，此时第3乘客只能坐1号座，失败。
  • 所以这一支的成功概率为 1/2。
• 选3号座：概率1/3。第3乘客的座位没了，最终一定失败。

总概率 = 1/3 × 1 + 1/3 × 1/2 + 1/3 × 0 = 1/3 + 1/6 = 1/2。

看出来了吗？第1个乘客选2号座时，问题退化为“2个空座（1号和3号），由第2个乘客随机决定谁赢”。1号和3号作为“终点”是对称的，所以成功概率 1/2。这就是“对称性”的雏形。

3.4 动态规划的思想迁移

虽然这道题用归纳法一步到位，但很多同学会想到用动态规划来解。严格来说，这题不是一道“动态规划题”，因为状态转移不依赖于“前缀选择”的最优性，而是依赖于概率的线性叠加。但我们可以用“概率DP”的框架来建模，设 dp[i] 表示“当前有 i 个尚未决定归属的座位，且其中一个特殊座位（第1个乘客的座位）和终点座位（第n个乘客的座位）都在其中时，终点座位最终能保留的概率”。

这种建模下，dp[i] 的转移是：

• 当前随机选择一个座位。
• 如果选到特殊座位或终点座位，游戏结束，成功与否立判。
• 如果选到其他座位，则那个座位的“主人”会变成新的随机选择者，但剩余空座中特殊座位和终点座位都还在，只不过空座数量减少1个。

于是 dp[i] = 1/i × 1（选到特殊座位，成功？错了，这里需要小心定义）

我们换一种更清晰的定义：当有 i 个空座，其中包含“保护目标座”T和“安全垫座”S时，当前有人要随机从 i 个空座中选一个。如果选中 T，则目标失败；如果选中 S，则目标成功（因为后续不会再有人乱选）；如果选中其他座位，则那个座位的乘客会接替随机选择，但此时空座变为 i-1 个，S和T依然都在。所以：

dp[i] = (1/i) * 0 + (1/i) * 1 + ((i-2)/i) * dp[i-1]

边界 dp[1] 不可能出现（因为S和T是两个不同座位，至少 i≥2），当 i=2 时，dp[2] = 1/2 * 0 + 1/2 * 1 = 1/2。

这个递推式解得 dp[i] 恒等于 1/2。其实它就是递归式的另一种写法。这个思路对以后理解“带吸收态的随机游走”很有帮助，算是这题给我们的额外红利。

4. 代码实现：三种写法，从入门到装逼

4.1 最简单：一行公式

既然证明了答案就是 1/2，那么代码简单到令人发指：

def nthPersonGetsNthSeat(n: int) -> float: return 1.0 if n == 1 else 0.5

但这只是“做题家”的答案。面试官如果看到你直接写这个，大概率会追问一句：“请证明一下。”所以只背结论是不够的，必须掌握上面的推导过程。

4.2 可复现的递归实现

如果你担心面试官不让你直接写公式，你可以把递归思想转换成代码。注意，这里递归的是“子问题人数”，而不是原题里的动态过程：

def nthPersonGetsNthSeat(n: int) -> float: if n == 1: return 1.0 # 直接使用归纳结果 return 0.5

当然，这只是伪递归。如果你真的想用递推式算 f(n)（比如不支持归纳结论的情况下），可以写成：

def nthPersonGetsNthSeat(n: int) -> float: if n == 1: return 1.0 # 用递推式：f(n) = 1/n * (1 + sum_{m=2}^{n-1} f(m)) # 但这会超时，除非优化。 # 所以我们直接返回 0.5 即可。 return 0.5

实际上，LeetCode上这题只需要返回 double，所以直接返回 0.5 就能通过。但为了展示“我懂原理”，你可以把归纳法的关键步骤写成注释，或者用 DP 求一遍再说“可以化简为 1/2”。这里我给出一个不带优化但展示思想的DP版本（仅用于加深理解，不推荐提交）：

def nthPersonGetsNthSeatDP(n: int) -> float: if n == 1: return 1.0 dp = [0.0] * (n + 1) dp[2] = 0.5 for i in range(3, n + 1): # f(i) = 1/i + (1/i) * sum_{j=2}^{i-1} f(j) s = sum(dp[2:i]) dp[i] = 1 / i + s / i return dp[n]

这个DP的复杂度是O(n^2)，不适合大数据，但它能验证归纳结论。你会发现 dp[n] 始终等于 0.5。如果题目n很大（比如10^9），O(n^2)直接爆炸，所以最终还是要回到数学解法。

4.3 蒙特卡洛模拟的改良版

前面说过，模拟可以帮助验证。如果想把模拟写得更高效，可以用“只记录被占座位集合”的方式，每次从剩余空座里随机选时，用random.choice(list(empty))，其中empty是一个集合。不过集合转列表也是O(n)，本质没变。更好的方法是模拟“链条”：

其实我们可以直接模拟那个随机链条，而不必为每个乘客分配座位。核心逻辑是：维护一个“当前乱坐的人”和他的“身份”。初始时，乱坐者是第1个乘客。当他乱坐到一个座位k时，如果k是1或者n，链条结束；如果k不是1或者n，那么第k个乘客会成为新的乱坐者。最后看链条结束时选中的是n还是1。

import random def simulate_chain(n): cur = 1 # 当前乱坐的乘客编号 while True: # 从剩余空座中随机选一个。在链条视角下，剩余空座就是集合 {1, cur+1, ..., n} # 但更简单的等价：cur 随机选一个座位，若选到非1非n的座位，则下一个乱坐者变成那个座位编号。 # 注意：这里的随机范围是 1..n 中尚未被坐的座位。但由于 cur 之前的乘客都坐自己的座位， # 尚未被坐的座位正是 {1, cur, cur+1, ..., n} 中的一部分？其实更准确地说： # 当乱坐者是 cur 时，空座为 {1, cur, cur+1, ..., n} 中去掉已被占的特殊座位。 # 为了避免复杂，我们在完整模拟中更清晰。 pass

这个链条模拟虽然代码不好写，但思想很重要。它是证明“对称性”的钥匙。所以我在实际验证时，还是用最朴素的完整模拟，反正n不大。

4.4 边界条件与精度问题

LeetCode的判题器会检查你的返回值与标准答案的误差。由于标准答案就是 0.5，直接返回 0.5 是精确的。需要注意 n=1 时返回 1.0，因为只有一个乘客，他随便坐也是自己的座位。这个边界条件很多人会漏掉，导致 n=1 时输出 0.5，直接WA。我见过不少题解在 n=1 的问题上翻车，所以提醒大家务必留意。

另外，如果你用浮点数，注意不要写return 1 / 2这种整数除法（在Python3里是0.5，没问题；但一些语言里会变成0，比如C++）所以最好写成0.5或者1.0 / 2。

5. 常见误区与面试追问

5.1 误区一：试图用“全排列”硬算

这题最容易想到的是枚举所有可能的“座位抢占关系”，然后统计第n个乘客坐到自己座位的排列数。但这样做的复杂度是O(n!)，n=10就跑不动了。而且这种枚举很容易重复计数，因为同一个座位分配结果可能对应多种随机选择的顺序吗？答案是“随机选择的顺序唯一决定分配结果”，所以枚举随机选择的“路径”是可以的，但路径数量爆炸。因此这条路走不通。

5.2 误区二：把“第1个乘客随机坐”当成“所有人都随机坐”

如果所有人都随机坐，那么第n个乘客坐到自己座位的概率就是1/n，这就错了。题目中除了第1个乘客，其他人都是“理性”的——有自己的座位就一定坐自己的。这个区别至关重要。所以题目名字虽然是“飞机座位分配”，但本质上是一个“占座破坏链”问题。

5.3 误区三：以为概率跟n有关

很多人直觉上觉得n越大，最后一个乘客坐到自己座位的概率越小，因为“前面搞乱的可能性越多”。但模拟和证明都告诉我们，概率恒定1/2。原因在于：不管n多大，真正决定命运的就是“第1个乘客的座位”和“第n个乘客的座位”谁先被乱坐选中，而这两个座位在整个过程中始终是对称的。

5.4 面试追问：如果是“第k个乘客”而不是最后一个呢？

这是一个非常好的变形。如果题目问的是“第k个乘客坐在自己座位上的概率”，答案就不再是1/2了。你可能会得到：

• 第1个乘客：当然是1，因为他随机坐，但随机坐也可能坐到自己座位，所以概率1/n？不对，题目问“坐在自己座位上”，第1个乘客的概率是1/n（随机选到自己的座位）。
• 第2个乘客：只有当第1个乘客坐了第2个座位时，他才需要随机选，否则坐自己座位。概率 = 1 - 1/n? 我们来算一下：第2个乘客坐自己座位的概率 = 第1个乘客没有坐第2个座位的概率 = (n-1)/n。
• 第k个乘客（k≥2）呢？这个就要小心了。其实答案是：如果 k < n，概率为 (n-k+1)/(n-k+2)？不对，我记着有个公式，LeetCode的讨论区有推导。实际上，第k个乘客（2≤k≤n）坐到自己座位的概率是 (n-k+2)/(n-k+1)? 这太奇怪了。让我们认真想一下。

其实这个问题是另一个经典：第k个乘客能坐到自己座位的概率。我印象中答案是：当 k=1 时 1/n；当 2≤k≤n 时，概率为 ((n-k+1)/(n-k+2))？拿n=3验证：第2个乘客坐自己座位的概率应该是 2/3？模拟一下：第1个随机坐，如果坐1号位（1/3），第2个坐2号位；如果坐2号位（1/3），第2个随机选1或3，只有选1才算坐自己座位？不对，第2个乘客的座位是2号，但2号已被占，所以他永远不会坐在2号自己的座位上。等等，题目问“坐在自己座位上”，如果座位被占，他只能坐别的，所以不可能坐在自己座位上。所以第2个乘客坐自己座位的概率 = 第1个乘客没坐2号座位的概率 = 1 - 1/n = 2/3（n=3时）。好的，这个简单。对于k≥3呢？推导会用到类似递归，但不是0.5。所以面试官如果把问题改成“第k个乘客”，难度就提升了。这里不展开，留给大家思考。

5.5 面试追问：如果飞机上有两个人同时乱坐呢？

这又是一个变种，可以设计成“第1个和第2个乘客都乱坐，后续按规则”。概率会变化，需要重新递推。这题的核心在于，乱坐的人数越多，不确定性越大，但答案可能依然是一个简洁的分数。面试时遇到这种变形，千万不要慌，回到“递推+对称性”的方法论，大概率能推出来。

6. 实操心得：这道题教会了我什么

最后分享一点个人感悟。在LeetCode上刷题，很多题目看题解觉得“不过如此”，但真正合上答案自己推一遍，才发现处处是坑。飞机座位分配这题，我第一次做的时候直接看题解，觉得“就这？”结果过了一周再遇到类似题，还是不会。后来我逼着自己从模拟到递归到归纳，完整走了一遍，才真正记住那个 1/2 是怎么来的。

我自己总结了一套“概率题三板斧”，每次遇到概率类题目都会用：

• 第一板斧：写模拟。哪怕很暴力，先知道答案的数值范围，避免推导方向错误。
• 第二板斧：找递推。把问题分解成“第一个随机选择”之后的各种情况，列出递推式。
• 第三板斧：归纳验证。从递推式推出通项，再用数学归纳法确认。

这套方法对很多概率DP和随机过程题目都适用，比如“扔骰子到达目标期望步数”、“随机游走吸收概率”等。所以1227虽然是一道easy题，但它的方法论价值不亚于medium甚至hard题。

如果你也想彻底掌握这类题，建议不要只背结论，而是亲手写一遍模拟，推一遍归纳。说实话，当你自己推出 f(n)=1/2 的那一刻，是很有成就感的。中途可能会绕弯路，比如我一开始也试图用全排列枚举，被n=8的复杂度劝退，但在那之后，我对“概率题不要枚举，要递推”的理解深刻了很多。

这题还有一个扩展玩法：用贝叶斯视角理解。当第1个乘客随机选座后，后面的每一次随机选座都是在“更新”对最终结果的信念，但无论怎么更新，后验概率始终是1/2。这种“观测不影响最终概率”的特性，有点像量子力学里的某些测量现象，当然只是类比，但能帮助你记住这个反直觉的结论。

最后再说一个实用技巧：如果你的面试官让你写这道题，建议你先说“我可以先给出O(1)的数学结论”，然后主动解释推导过程。面试官通常更喜欢听到“为什么”，而不是看到你直接甩一行返回0.5。把递推式写在白板上，再用归纳法证明，这一套组合拳下来，offer概率至少能提高几个百分点吧（笑）。

总之，飞机座位分配这道题，是少有的“越品越有味”的概率题。下一篇我准备聊聊它的变种“第k个乘客”的完整推导，以及如何把这种递推思想迁移到其他LeetCode概率题上，感兴趣的朋友可以在评论区留言交流。