1227. 飞机座位分配概率

题目

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

剩下的乘客将会：

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

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

分析

借用 0x3f 的题解^[1227题解. - 力扣（LeetCode）]的图片：

整体的思路很容易理解，关键是递推公式的证明：

$$f(n)=\frac{1}{n}+\frac{1}{n}\times (f(n-1)+f(n-2)+\cdots +f(2))$$

把式子两边同乘 n，得

$$nf(n)=f(n-1)+f(n-2)+\cdots +f(2)+1$$

对于 n−1，有

$$(n-1)f(n-1)=f(n-2)+\cdots +f(2)+1$$

两个式子相减得

$$nf(n)-(n-1)f(n-1)=f(n-1)$$

整理得

$$nf(n)=nf(n-1)$$

即

$$f(n)=f(n-1)$$

所以

$$f(n)=f(n-1)=f(n-2)=\cdots =f(2)=\frac{1}{2}$$