1. 题目到底在问什么一个让无数人栽跟头的“简单”概率题先说说我自己的经历。第一次在LeetCode上看到1227这道题时我以为是道送分题飞机座位分配这不就是个排列组合吗结果动手一写才发现完全不是那么回事。题目描述很简短但里面藏着一个特别反直觉的概率结论——第n个乘客坐在自己座位上的概率居然恒等于1/2跟n有多大没关系。很多人在评论区吵翻了天有人用蒙特卡洛模拟验证有人推公式推到怀疑人生还有人说这题应该归为“脑筋急转弯”而不是“动态规划”。但我觉得这道题恰恰是理解“概率转移”和“状态压缩”的绝佳素材比很多hard题都值得仔细咀嚼。先看题目原意一架飞机有n个座位编号1到n。第1个乘客找不到自己的登机牌或者干脆丢了于是他随机选一个座位坐下。后面的乘客按顺序登机如果自己的座位还空着就坐自己的座位如果自己的座位被占了就随机在剩余空座里挑一个。问第n个乘客也就是最后一个乘客恰好坐在自己座位上的概率是多少注意几个关键约束第1个乘客是随机乱坐的这一点是整个问题的“原罪”。后面的乘客都是“理性”的只有在座位被占时才随机乱选。最后一个乘客没有任何选择余地他只能坐剩下的那个座位——所以问题等价于“最后一个剩下的座位恰好是第n个乘客自己的座位的概率”。这道题之所以经典是因为它表面上看起来像一个递推概率问题但实际上可以用极其简洁的数学归纳法解决。更妙的是答案与n无关永远是1/2n1时除外概率为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, trials100000): ok 0 for _ in range(trials): if simulate_once(n): ok 1 return ok / trials for n in [2, 3, 5, 10, 100]: print(fn{n}, probability{simulate(n):.4f})跑出来的结果大概是这样n模拟概率10万次理论值11.0000120.50061/230.49921/250.50181/2100.49761/21000.50031/2看到没不管n是3还是100概率都稳定在0.5附近。这个结果本身就很有意思——如果这题的结果随n变化比如1/n或者1/n!那模拟也会给出对应的趋势。但稳定在1/2说明背后一定有一个非常简洁的对称性或者不变性在起作用。2.2 模拟代码的复杂度问题上面的模拟代码虽然正确但效率很低。每次随机选空座都扫描整个数组复杂度O(n^2)n100时还好n10000就非常慢了。如果只是验证结论可以接受但如果你想用模拟来“证明”答案那在效率上就有点说不过去。优化方法也很简单用集合维护空座索引或者用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个乘客的座位、第k1到第n个乘客的座位以及……等等还需要把第k个乘客随机选座后的情况继续推演下去。这里如果直接展开会陷入一个“乘客不断被挤走”的链条。但我们可以做一个关键的等价变换当第k个乘客被迫随机选座时他面对的局面其实和“一个新的问题”非常像——只不过这个新问题里第k个乘客扮演了当初第1个乘客的角色而“第n个乘客的座位”依然是那个需要保住的座位。具体来说当第k个乘客随机选座时剩余空座的集合是第1个乘客的座位、第k1个座位、……、第n个座位共n-k1个空座。如果第k个乘客恰好选择了第k1个座位那么第k1个乘客登机时也会面临同样的困境继续随机选。依此类推直到某个乘客选到第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-k1且有一个“占座者”第1个乘客的座位是特殊的。最后一个乘客能坐到自己座位的概率等价于 f(n-k1)……吗这里要小心。直接写成 f(n-k1) 其实不太严谨因为子问题的“第一个乱坐的人”可能不是第k个乘客本人而是第1个乘客。但我们可以把视角切换一下当第k个乘客登机时他发现自己座位被占要随机选座。如果把第k个乘客看作“新的乱坐者”那么他面对的剩余空座集合是 {第1个乘客的座位, 第k1个座位, ..., 第n个座位}。这个集合里有 n-k1 个座位其中“第n个乘客的座位”就是需要保住的座位。这和原始问题n-k1个乘客第一个乘客乱坐的结构完全一致——都是“第一个乱坐的人随意选一个座位后续按规则坐”。所以子问题的概率确实等于 f(n-k1)。于是递推式f(n) 1/n × 1 1/n × 0 (1/n) × Σ_{k2}^{n-1} f(n-k1)令 m n-k1当 k 从 2 到 n-1 时m 从 n-1 到 2。所以f(n) 1/n (1/n) × Σ_{m2}^{n-1} f(m)接下来就是数学归纳法的舞台。3.2 归纳证明三步走我们用归纳法证明对所有 n ≥ 2f(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) × Σ_{m2}^{n-1} f(m) 1/n (1/n) × Σ_{m2}^{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 更直观的“三乘客”特例分析为了让大家彻底理解我拿 n3 手算一遍。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当 i2 时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_{m2}^{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_{j2}^{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^9O(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, cur1, ..., n} # 但更简单的等价cur 随机选一个座位若选到非1非n的座位则下一个乱坐者变成那个座位编号。 # 注意这里的随机范围是 1..n 中尚未被坐的座位。但由于 cur 之前的乘客都坐自己的座位 # 尚未被坐的座位正是 {1, cur, cur1, ..., n} 中的一部分其实更准确地说 # 当乱坐者是 cur 时空座为 {1, cur, cur1, ..., n} 中去掉已被占的特殊座位。 # 为了避免复杂我们在完整模拟中更清晰。 pass这个链条模拟虽然代码不好写但思想很重要。它是证明“对称性”的钥匙。所以我在实际验证时还是用最朴素的完整模拟反正n不大。4.4 边界条件与精度问题LeetCode的判题器会检查你的返回值与标准答案的误差。由于标准答案就是 0.5直接返回 0.5 是精确的。需要注意 n1 时返回 1.0因为只有一个乘客他随便坐也是自己的座位。这个边界条件很多人会漏掉导致 n1 时输出 0.5直接WA。我见过不少题解在 n1 的问题上翻车所以提醒大家务必留意。另外如果你用浮点数注意不要写return 1 / 2这种整数除法在Python3里是0.5没问题但一些语言里会变成0比如C所以最好写成0.5或者1.0 / 2。5. 常见误区与面试追问5.1 误区一试图用“全排列”硬算这题最容易想到的是枚举所有可能的“座位抢占关系”然后统计第n个乘客坐到自己座位的排列数。但这样做的复杂度是O(n!)n10就跑不动了。而且这种枚举很容易重复计数因为同一个座位分配结果可能对应多种随机选择的顺序吗答案是“随机选择的顺序唯一决定分配结果”所以枚举随机选择的“路径”是可以的但路径数量爆炸。因此这条路走不通。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-k1)/(n-k2)不对我记着有个公式LeetCode的讨论区有推导。实际上第k个乘客2≤k≤n坐到自己座位的概率是 (n-k2)/(n-k1)? 这太奇怪了。让我们认真想一下。其实这个问题是另一个经典第k个乘客能坐到自己座位的概率。我印象中答案是当 k1 时 1/n当 2≤k≤n 时概率为 ((n-k1)/(n-k2))拿n3验证第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/3n3时。好的这个简单。对于k≥3呢推导会用到类似递归但不是0.5。所以面试官如果把问题改成“第k个乘客”难度就提升了。这里不展开留给大家思考。5.5 面试追问如果飞机上有两个人同时乱坐呢这又是一个变种可以设计成“第1个和第2个乘客都乱坐后续按规则”。概率会变化需要重新递推。这题的核心在于乱坐的人数越多不确定性越大但答案可能依然是一个简洁的分数。面试时遇到这种变形千万不要慌回到“递推对称性”的方法论大概率能推出来。6. 实操心得这道题教会了我什么最后分享一点个人感悟。在LeetCode上刷题很多题目看题解觉得“不过如此”但真正合上答案自己推一遍才发现处处是坑。飞机座位分配这题我第一次做的时候直接看题解觉得“就这”结果过了一周再遇到类似题还是不会。后来我逼着自己从模拟到递归到归纳完整走了一遍才真正记住那个 1/2 是怎么来的。我自己总结了一套“概率题三板斧”每次遇到概率类题目都会用第一板斧写模拟。哪怕很暴力先知道答案的数值范围避免推导方向错误。第二板斧找递推。把问题分解成“第一个随机选择”之后的各种情况列出递推式。第三板斧归纳验证。从递推式推出通项再用数学归纳法确认。这套方法对很多概率DP和随机过程题目都适用比如“扔骰子到达目标期望步数”、“随机游走吸收概率”等。所以1227虽然是一道easy题但它的方法论价值不亚于medium甚至hard题。如果你也想彻底掌握这类题建议不要只背结论而是亲手写一遍模拟推一遍归纳。说实话当你自己推出 f(n)1/2 的那一刻是很有成就感的。中途可能会绕弯路比如我一开始也试图用全排列枚举被n8的复杂度劝退但在那之后我对“概率题不要枚举要递推”的理解深刻了很多。这题还有一个扩展玩法用贝叶斯视角理解。当第1个乘客随机选座后后面的每一次随机选座都是在“更新”对最终结果的信念但无论怎么更新后验概率始终是1/2。这种“观测不影响最终概率”的特性有点像量子力学里的某些测量现象当然只是类比但能帮助你记住这个反直觉的结论。最后再说一个实用技巧如果你的面试官让你写这道题建议你先说“我可以先给出O(1)的数学结论”然后主动解释推导过程。面试官通常更喜欢听到“为什么”而不是看到你直接甩一行返回0.5。把递推式写在白板上再用归纳法证明这一套组合拳下来offer概率至少能提高几个百分点吧笑。总之飞机座位分配这道题是少有的“越品越有味”的概率题。下一篇我准备聊聊它的变种“第k个乘客”的完整推导以及如何把这种递推思想迁移到其他LeetCode概率题上感兴趣的朋友可以在评论区留言交流。