https://leetcode.com/problems/airplane-seat-assignment-probability/
n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:- Take their own seat if it is still available,
- Pick other seats randomly when they find their seat occupied
What is the probability that the n-th person can get his own seat?
Example 1:
Input: n = 1 Output: 1.00000 Explanation: The first person can only get the first seat.
Example 2:
Input: n = 2 Output: 0.50000 Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).
Constraints:
1 <= n <= 10^5
Q: Say if there are
A: For any case, we can get rid of those sitting on own seats (except the first passenger) and get a problem of
Except
n passengers and the first passenger took the 3rd seat. Now, like you explained, there are n - 1 passengers and n - 1 seats left. But when the 2nd passenger comes in, he doesn't have 2 options to make it possible for the nth passenger to take the nth seat. Instead, he only has one option, which is to take the 2nd seat because it is not occupied by the first passenger. I don't see how that is the case of a subproblem of (n - 1). Could you shed some light please, thanks!A: For any case, we can get rid of those sitting on own seats (except the first passenger) and get a problem of
n' (= n - k, where k is the number of passengers sitting on own seats), then re-number (without changing the relative order) them as passenger 1, 2, ..., n', hence the result is in same form, the only difference is to change n to n'.Except
n' = 1, results for n' of other values are independent on n'. In short, changing from n to n' will not influence the result.Part 1: [Java] 2 liners w/ explanation and analysis.
For the
1st passenger, there are 2 cases that the nth passenger could take the right seat:1st passenger- Take his own seat, the probability is
1 / n; - Take a seat neither his own nor the one of the
nthpassenger, and thecorrespondingprobability is(n - 2) / n; In addition, other passengers (except thenthone) should not occupy thenthseat;
Now there aren - 1passengers andn - 1seats remaining, and the2ndpassenger, like the1stone, have2options to make it possible thenthpassenger take the right seat:
a) take the1stpassenger's seat, the probability is1 / (n - 1);
b) Take a seat that is neither the1stpassenger's nor thenthpassenger's, and thecorrespondingprobability is((n - 1) - 2) /( n - 1);
Obviouly, we recurse to subproblem of(n - 1).
Combined the above
2 cases, we have the following code: public double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1.0d;
return 1d / n + (n - 2d) / n * nthPersonGetsNthSeat(n - 1);
}
Analysis
Time: O(n), space: O(1).
Time: O(n), space: O(1).
Based on the code in part 1, we have the following formula:
f(n) = 1 / n + (n - 2) / n * f(n - 1)
Part2: Proof when n > 1, the f(n) is 1/2
n = 2, we havef(2) = 1/2; the assumption holds;- Suppose
n = kwe havef(k) = 1/2, whenn = k + 1,
f(k + 1) = 1 / (k + 1) + (k + 1 - 2) / (k + 1) * f(k)
= 2 / (2 * (k + 1)) + (k - 1) / (k + 1) * 1/2
= 1 / 2
That is,
f(k + 1) = 1 / 2 also holds.
From above 1 and 2, we complete the proof.
With the conclusion, it is easy to have 1 liners for Java and Python 3:
public double nthPersonGetsNthSeat(int n) {
return n == 1 ? 1.0d : .5d;
}
def nthPersonGetsNthSeat(self, n: int) -> float:
return 1.0 if n == 1 else 0.5
Each round we have 3 choices:
- the 1st person gets his/her own seat. (with probability
1/n). Then the n-th person is sure (with probability1) to get the n-th seat. - the 1st person gets the n-th person's seat. (with probability
1/n). Then the n-th person cannot (with probability0) get the n-th seat. - the 1st person gets a seat between
2andn-1(with probability(n-2)/n). Assume the 1st person gets a-th seat. Then in the next round, we have 3 choices again:
3.1) if the a-th person gets 1st seat (with probability1/(n-1)), then this is just like 1st and a-th person swap their seats, it never affect our result for the n-th person.
3.2) if the a-th person gets n-th seat (with probability1/(n-1)), game over.
3.3) if the a-th person gets a seat which is not 1st or n-th, (with probability(n-1-2)/(n-1)), we jump into a loop.
Therefore the dp pattern is
dp[i] = 1.0 / (i+1) + 0.0 / (i+1) + dp[i-1] * (i-1) / (i+1), with dp[0]=1 for the case there's only one person. If you manually calculate it you'll find dp[i] is always 1/2 except the base condition.class Solution(object):
def nthPersonGetsNthSeat(self, n):
"""
:type n: int
:rtype: float
"""
# return 0.5 if n > 1 else 1.0
dp = [0] * n
dp[0] = 1.0
for i in xrange(1, n):
dp[i] = 1.0 / (i+1) + dp[i-1] * (i-1) / (i+1)
return dp[-1]https://www.cnblogs.com/onePunchCoder/p/11699121.html
n个用户依次登机就坐。第一个用户丢失了机票，将会随机选取一个座位，之后的乘客优先坐自己的座位，如果自己座位被占了则随机找寻一个座位就坐，求问第n个用户得到自己座位的概率。
2、分析与证明
- 假设有n个用户，本问题的答案为 f(n)。
- 如果第一个人随机到了自己的位置，那么后面的人一定按自己机票座位号入座。
- 如果第一个人随机到了第n个人的位置，那么第 n 个人得到自己座位的概率为0。
- 如果第一个人随机到了第2个人的位置，那么第 n 个人得到自己座位的概率为f(n-1)。
- 依次类推可得 f(n) = (1 + f(n-1) + f(n-2) + ... + f(2) + 0) / n ;
- 假设当 1< i <= k 时 f(i) = 1/2 , 容易证明f(k+1) = 1/2; 所以f(n) 在n > 1的时候恒等于 1/2 .
论证过程的代码实现如下
public double nthPersonGetsNthSeat(int n) {
if(n==1) return 1.0;
double[] dp = new double[n];
double sum = 0;
for (int i = 1; i < n; i++) {
dp[i] = (1 + sum) / (i + 1);
sum += dp[i];
}
return dp[n - 1];
}
