一、題目描述

有 n 位乘客即將登機，飛機正好有 n 個座位。第一位乘客的票丟了，他隨便選了一個座位坐下。

剩下的乘客將會：

• 如果他們自己的座位還空著，就坐到自己的座位上，
• 當他們自己的座位被占用時，隨機選擇其他座位

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

示例 1：

輸入：n = 1 輸出：1.00000 解釋：第一個人只會坐在自己的位置上。 示例 2： 輸入: n = 2 輸出: 0.50000 解釋：在第一個人選好座位坐下后，第二個人坐在自己的座位上的概率是 0.5。

提示：

1 <= n <= 10^5

二、解題思路 & 代碼

直觀的想法：

除了第一個人，當第 i 個人選完座位后，第 i 個座上面一定有人，這樣到最后只有第 n 個和第 1 個座位上存在不確定性。

嚴謹推導：

首先題目并沒有說第一個乘客座位號就是 1 啊？也沒說最后一個乘客座位號就是 n 啊？所以大家的假設是怎么來的？這一點沒有說清。其實很簡單，不管每個乘客編號是多少，我們不用管，我們只要看他入場的次序就行了，所以我們就按照入場次序給他們重新編個號，這樣的話就是按照 1 到 n 的編號入場了（也就是這里的編號代表的是入場的次序，而不是實際的座位號）。

然后就是 1 號進場了，可以分為下面幾種情況：

他有 $\frac{1}{n}$ 的概率選擇坐在 1 號座位上。這樣 2 到 n 號位置都不會被占，那么 n 號坐在自己座位的概率就是 1.0 。

他有 $\frac{1}{n}$ 的概率選擇坐在 n 號座位上。這樣 2 到 n-1 號位置都不會被占，而 n 號只能坐在 1 號座位上，那么概率就是 0.0 。

他有 $\frac{1}{n}$ 的概率選擇坐在 i 號座位上，其中 $2\le i\le n?1$。這樣 2 到 i?1 號位置都不會被占，他們都坐在自己的的位置上。而 i 號乘客就犯難了，他的座位被 1 號占了，他不知道坐哪了。這時候，如果他選擇坐 1 號座位，那么 i+1 到 n 號乘客還是坐在自己位置，相安無事。而如果他選擇坐在i+1 到 n 號中的某個位置，那么必然又會產生新的沖突，這樣就不好求解了啊！

對于第三種情況，我們可以換個角度看問題。現在面臨的問題是，i 號選擇坐在哪？這時候還沒入場的有 i 到 n 號乘客，而座位還剩 1 和 i+1 到 n 號。那既然 i 號乘客坐在 1 號座位的話，后面的人都能坐回原位，那我們就把 1 號座位當作是 i 號乘客原本的座位就行了嘛，反正我最后又不要求 i 號乘客坐回原位的概率，你坐哪都沒事，只要別影響到其他人就行了。那么問題的規模就被縮小到了 n?i+1 ，我們遞歸求解就行了。

令 $f(n)$ 表示 n 個人的情況下，最后一個人坐回原位的概率，按照上面的分析，我們可以列出遞推式：

$$f(n)=\frac{1}{n}\left(1+\sum _{i=2}^{n?1}f(n?i+1)\right)$$

這個遞推式想必大家高中就會求了，令 $n=n?1$ 再寫出一項：
$$f(n?1)=\frac{1}{n?1}\left(1+\sum _{i=2}^{n?2}f(n?i)\right)$$

然后兩式相減得到：

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

即：
$$f(n)=f(n?1)=?=f(2)$$

那么我們就可以得到最終的答案了，對任意的 $n\ge 2$ 都有
$$f(n)=f(2)=0.5$$

還有一個特例就是$f(1)=1.0$ ，這樣這題就證好了。

關鍵：

這題最關鍵的一步就是 1 號坐在了 i 號座位后，i 號何去何從？如果你能換個角度，把 1 號座位給 i 號（因為給他之后，對后面的乘客座位沒有任何影響，那么就能把 1 號座位看成就是 i 號乘客的），那么問題就能遞歸下去了。題解區許多人這一步為什么能遞歸下去？根本沒有講清楚。

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

參考：

LeetCode優秀題解

飛機座位分配概率（dp 思路）

總結

以上是生活随笔為你收集整理的【LeetCode】1227. 飞机座位分配概率的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。