飞机座位分配概率

题目链接:https://leetcode.cn/problems/airplane-seat-assignment-probability/

面对这道题首先寻找规律

• n=1 时答案显然为 1
• n=2 时，1/2 概率，1 号坐在一号位，那么 2 号自然坐 2 号位符合题意。1/2 概率，1 号坐在 2 号位，不符合题意。由此 n=2 时，答案为 1/2
• n=3 时，首先 1/3 概率，1 号坐一号位，符合题意。1/3 概率，1 号坐 2 号位，其中 1/2 可能性，2 号坐 1 号位，3 号坐 3 号位符符合题意。由此 n=3 时答案为 1/3+1/6，答案为 1/2

根据上述思路可以推得 f(n)=(1/n)+((n-2)(f(n-1))(1/n)) 这就是 dp 的递推公式

这里给出 ts 的示例代码

function nthPersonGetsNthSeat(n: number): number {
    if (n === 1) return 1;
    let dp = new Array(n).fill(0);
    dp[0] = 1;
    for (let i = 1; i < n; i++) {
        dp[i]=(1/(i+1))+(i-1)*((1/(i+1))*dp[i-1])
    }
    return dp[n - 1]
}

另外，尝试开始几个数之后会发现 n>1 时的答案都是 1/2 所以代码也可以如下书写

function nthPersonGetsNthSeat(n: number): number {
    let dp=
    if(n==1){
        return 1
    }else{
        return 0.5
    }
};