题目

该题是中文网站的 LeetCode 的 1227题，题目如下：

思路

自己想的情况还是有欠缺的地方，最后是看题解后总结出来的，记录一下。

思路1：

假设第一位没票的客人先上飞机，整体分3种情况：

  • 1.第一位客人选的是他本来应该座的位置，其他人都有票，对号入座即可。
    第 n 位乘客坐在自己的座位上的概率是： 1 / n * 1。

  • 2.第一位客人选的是第n位客人的位置，这样第n位客人无论无何都座不到自己本来的位置。
    第 n 位乘客坐在自己的座位上的概率是： 1 / n * 0。

  • 3 第一位客人即没选本来应该的位置，也没选第n位客人应该座的位置。那这种情况下 第2位到第n-1位客人肯定有1个人的位置是被第1位客人座了，设这个人是第i位客人。
    那这时第i位客人的选择也会影响到第n位客人是否能做到自己本来的位置，情况也是以上分析的3种情况。
    我们可以这样想:
    把第i位客人当着这轮的“第1位客人”来看待，整个座位的个数是n-1个。也就是把问题的范围缩小了，由原来的n个人，缩小到现在的n-1人。
    先暂且假设知道这时候 “第 i 位乘客坐在自己的座位上的概率” 是dp[n-1]。
    所以： 这第3种情况下：第 n 位乘客坐在自己的座位上的概率是： (n-2) / n * dp[n-1]

    所以，最后总的概率就是把以上3种情况的概率加起来即可。

思路2：
  • 一：先看大于 2 个客人时的情况：
    因为题目没有说 n 个客人是以什么要的顺序来上飞机选座位的。
    我们就先让 第 2 位 到 第 n-1 位的客人上飞机，因为他们都是有票的，100% 会做到自己的位置。
    那么就只剩下了 第 1 位 、 第 n 位客人了，就是简化到了只有2个客人的情况，概率是 0.5
  • 二：再看只有 1 个人的情况，概率是 1
  • 三：最后，直接用代码判断返回即可。

代码

    public double nthPersonGetsNthSeat(int n) {
   
        // dp 矩阵，不用下标为 0 的位置 。
        // dp[i] : 代表总共由 i 个客人时，第 i 位乘客坐在自己的座位上的概率为 dp[i] 。
        double[] dp = new double[n + 1];
        dp[1] = 1;      // 最基本的情况。

        for (int i = 2; i < dp.length; i++) {
   
            // 第 1 种情况 + 第 3 种情况的概率。 第 2 种情况的概率为 0
            dp[i] = 1.0 / i + (double) (i - 2) / i * dp[i - 1];
        }

        // 直接返回总共 n 个人时的情况下的概率。
        return dp[n];
    }