What is the pattern used in Airplane Seat Assignment Probability?

The pattern is a state transition dynamic programming approach where each passenger's probability depends on previous seat selections.

Why is the probability 0.5 for n > 1?

Because the first passenger's random seat choice either blocks the last seat or leaves it untouched, making the outcome equally likely.

Can I solve this problem without recursion?

Yes, an iterative DP approach or direct mathematical observation allows computing the probability efficiently without recursion.

What are common mistakes to avoid?

Ignoring the first passenger's impact, simulating all permutations, or misapplying the state transition formula are typical pitfalls.

Does GhostInterview provide a closed-form solution?

Yes, it can recognize the constant probability simplification and return f(n) = 0.5 for n > 1 instantly.

#1227

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

飞机座位分配概率

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。剩下的乘客将会：如果他们自己的座位还空着，就坐到自己的座位上，当他们自己的座位被占用时，随机选择其他座位第 n 位乘客坐在自己的座位上的概率是多少？示例 1：输入： n = 1 输出： 1.000…

数学动态规划脑筋急转弯概率与统计

题目描述

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

提示：

1 <= n <= 10^5

lightbulb

解题思路

方法一：数学

用 $f(n)$ 表示当有 $n$ 位乘客登机时，第 $n$ 位乘客坐在自己的座位上的概率。从最简单的情况开始考虑：

当 $n=1$ 时，只有 $1$ 位乘客和 $1$ 个座位，因此第 $1$ 位乘客只能坐在第 $1$ 个座位上， $f(1)=1$ ；

当 $n=2$ 时，有 $2$ 个座位，每个座位有 $0.5$ 的概率被第 $1$ 位乘客选中，当第 $1$ 位乘客选中座位之后，第 $2$ 位乘客只能选择剩下的座位，因此第 $2$ 位乘客有 $0.5$ 的概率坐在自己的座位上， $f(2)=0.5$ 。

当 $n>2$ 时，如何计算 $f(n)$ 的值？考虑第 $1$ 位乘客选择的座位，有以下三种情况。

第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择第 $1$ 个座位，则所有乘客都可以坐在自己的座位上，此时第 $n$ 位乘客坐在自己的座位上的概率是 $1.0$ 。
第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择第 $n$ 个座位，则第 $2$ 位乘客到第 $n-1$ 位乘客都可以坐在自己的座位上，第 $n$ 位乘客只能坐在第 $1$ 个座位上，此时第 $n$ 位乘客坐在自己的座位上的概率是 $0.0$ 。
第 $1$ 位乘客有 $\frac{n-2}{n}$ 的概率选择其余的座位，每个座位被选中的概率是 $\frac{1}{n}$ 。假设第 $1$ 位乘客选择第 $i$ 个座位，其中 $2 \le i \le n-1$ ，则第 $2$ 位乘客到第 $i-1$ 位乘客都可以坐在自己的座位上，第 $i$ 位乘客到第 $n$ 位乘客的座位不确定，第 $i$ 位乘客会在剩下的 $n-(i-1)=n-i+1$ 个座位中随机选择（包括第 $1$ 个座位和第 $i+1$ 个座位到第 $n$ 个座位）。由于此时剩下的乘客数和座位数都是 $n-i+1$ ，有 $1$ 位乘客会随机选择座位，因此问题规模从 $n$ 减小至 $n-i+1$ 。

结合上述三种情况，可以得到 $f(n)$ 的递推式：

\begin{aligned} f(n) &= \frac{1}{n} \times 1.0 + \frac{1}{n} \times 0.0 + \frac{1}{n} \times \sum_{i=2}^{n-1} f(n-i+1) \\ &= \frac{1}{n}(1.0+\sum_{i=2}^{n-1} f(n-i+1)) \end{aligned}

上述递推式中， $i$ 的取值个数有 $n-2$ 个，由于 $i$ 的取值个数必须是非负整数，因此只有当 $n-2 \ge 0$ 即 $n \ge 2$ 时，上述递推式才成立。

如果直接利用上述递推式计算 $f(n)$ 的值，则时间复杂度为 $O(n^2)$ ，无法通过全部测试用例，因此需要优化。

将上述递推式中的 $n$ 换成 $n-1$ ，可以得到递推式：

f(n-1) = \frac{1}{n-1}(1.0+\sum_{i=2}^{n-2} f(n-i))

上述递推式中， $i$ 的取值个数有 $n-3$ 个，只有当 $n-3 \ge 0$ 即 $n \ge 3$ 时，上述递推式才成立。

当 $n \ge 3$ 时，上述两个递推式可以写成如下形式：

\begin{aligned} n \times f(n) &= 1.0+\sum_{i=2}^{n-1} f(n-i+1) \\ (n-1) \times f(n-1) &= 1.0+\sum_{i=2}^{n-2} f(n-i) \end{aligned}

将上述两式相减：

\begin{aligned} &~~~~~ n \times f(n) - (n-1) \times f(n-1) \\ &= (1.0+\sum_{i=2}^{n-1} f(n-i+1)) - (1.0+\sum_{i=2}^{n-2} f(n-i)) \\ &= \sum_{i=2}^{n-1} f(n-i+1) - \sum_{i=2}^{n-2} f(n-i) \\ &= f(2)+f(3)+...+f(n-1) - (f(2)+f(3)+...+f(n-2)) \\ &= f(n-1) \end{aligned}

整理后得到简化的递推式：

\begin{aligned} n \times f(n) &= n \times f(n-1) \\ f(n) &= f(n-1) \end{aligned}

由于已知 $f(1)=1$ 和 $f(2)=0.5$ ，因此当 $n \ge 3$ 时，根据 $f(n) = f(n-1)$ 可知，对任意正整数 $n$ 都有 $f(n)=0.5$ 。又由于 $f(2)=0.5$ ，因此当 $n \ge 2$ 时，对任意正整数 $n$ 都有 $f(n)=0.5$ 。

由此可以得到 $f(n)$ 的结果：

f(n) = \begin{cases} 1.0, & n = 1 \\ 0.5, & n \ge 2 \end{cases}

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1 if n == 1 else 0.5

speed

复杂度分析

指标	值
时间	complexity is O(n) for iterative or recursive computation but reduces to O(1) using the mathematical simplification. Space complexity is O(1) if storing only the current probability value, otherwise O(n) for full DP array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate identifies the base cases f(1) and f(2) quickly.
question_mark
Look for recognition of the state transition pattern in seat selection probabilities.
question_mark
Evaluate if the candidate can simplify to the constant probability insight for n > 1.

warning

常见陷阱

外企场景

error
Ignoring the first passenger's random choice effect on subsequent probabilities.
error
Attempting full permutation simulation, which is unnecessary and inefficient.
error
Failing to correctly implement the state transition formula f(n) = 1/n + (n-2)/n * f(n-1).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the probability if the first k passengers choose randomly instead of only the first passenger.
arrow_right_alt
Determine the expected number of displaced passengers using similar DP state transitions.
arrow_right_alt
Extend the problem to a plane with multiple seat classes affecting passenger choices.

help

常见问题

外企场景

继续练习

#1025 除数博弈 #1467 两个盒子中球的颜色数相同的概率 #837 新 21 点