1227. 飞机座位分配概率

Problem: 1227. 飞机座位分配概率

思路

由于这道题后面人的选择对前面人的选择没有影响，而且题目中隐约可以看出存在利用更小规模的最优子结构来求解的可能，这道题可以尝试用动态规划的思路来求解，设f(n)为截止到第n个人时，第n个人坐到自己位置的概率。

这样，当n>=3时，就可以根据第一个人坐的情况分为三种情况：

1. 坐到自己的位置，$\frac 1n$的概率，此时n坐到自己位置的概率为1。
2. 坐到n的位置，$\frac 1n$的概率，此时n坐到自己位置的概率为0。
3. 坐到其他的位置，每个位置$\frac 1n$的概率，设该位置为i，则1之后、i之前的位置一定是正确的，1和i之后一共有n - i + 1个位置，同时还有同样多的人没有入场，而且第i号面临和1一样的情况，即他也要随机坐一个位置，并且他不是最后一个人，因此转换为规模为n - i + 1的子问题。

这样，就可以得出递推式，将n-1带入递推式，再将两式相减即可求出解。

详见官解。

踩坑

当时觉得动态规划难解，没有想出正确的最优子结构，就开始选择尝试模拟所有情况来暴力求解，但是这样时间复杂度非常高（阶乘）。在做题的时候一定不能蛮做，首先要排除时间复杂度不够的做法，如果全是不够的话需要看是否没有找出其中的数学关系。

复杂度

• 时间复杂度: $O(1)$
• 空间复杂度: $O(1)$

Code

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1 : 0.5;
    }
}