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

Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        

Solutions:
class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		return 1 / min(n, 2.0)


class Solution:

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


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1.0
		if n == 2:
			return 0.5
		return 0.5
		if n == 3:
			return 1 / 3 * 1 + 1 / 3 * 1 / 2 + 1 / 3 * 0
		if n == 4:
			return 1 / 4 * 1 + 1 / 4 * (1 / 3 * 1 + 1 / 3 * 1 / 2 + 1 / 3 * 0) + 1 / 4 * (1 / 3 * 1 + 1 / 3 * 1 + 1 / 3 * 0) + 1 / 4 * 0
		return 1 / n * 1 + (n - 2) / n * self.nthPersonGetsNthSeat(n - 2) + 1 / n * 0


import numpy as np

class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		return 1 / 2


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		s = 0
		for i in range(1, n - 1):
			s += 0.5 / n
		return 1 / n + s


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		res = 1.0
		cur = 1.0
		for i in range(2, n + 1):
			res = 1 / i * cur
			cur += res
		return res


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		if n == 2:
			return 0.5
		dp = [0] * n
		dp[0] = 1 / n
		for i in range(1, n - 1):
			dp[i] = 0.5 / n
		return sum(dp)


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		i = 0
		if n == 1:
			return 1
		notCorrect = 1 / n
		for i in range(1, n - 1):
			notCorrect *= 1.0 + 1.0 / (n - i)
		return 1 - notCorrect


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1.0
		sum_results = 0.0
		for i in range(2, n + 1):
			p = 1 / i * (1 + sum_results)
			sum_results += p
		return p


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		return 1 / 2


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		mem = {}
		mem[1] = 1.0
		mem[2] = 0.5
		for i in range(3, n + 1):
			mem[i] = mem[i - 1]
		return mem[n]


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1.0
		if n == 2:
			return 0.5
		dp = [1.0, 0.5]
		acc = 1.5
		for i in range(3, n + 1):
			dp.append(acc / i)
			acc += dp[-1]
		return dp[-1]


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		if n == 2:
			return 0.5
		result = 1.0
		curr = 1.0
		for i in range(2, n + 1):
			result = 1 / i * curr
			curr += result
		return result


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		good = 0
		left = n
		uncenrtain = 1
		while left >= 2:
			good += uncenrtain / left
			uncenrtain = uncenrtain * (left - 2) / left
			left -= 1
		return good


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		else:
			dp = [0 for _ in range(n + 1)]
			dp[n] = 1 / n
			for i in range(n - 1, 1, -1):
				dp[i] = dp[i + 1] / i + dp[i + 1]
			return dp[2]


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		p = [None, 1.0, 0.5]
		for i in range(2, n):
			prob = (i * p[i] + p[i]) / (i + 1)
			p.append(prob)
		return p[n]


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		P = [None] * (n + 1)
		P[2] = 1 / n
		for i in range(3, n + 1):
			P[i] = P[i - 1] * (1 + 1 / (n - i + 2))
		return P[n]


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		D = [0] * n
		D[0] = 1.0
		for i in range(1, n):
			D[i] = 1 / (i + 1) + (i - 1) / (i + 1) * D[i - 1]
		return D[-1]


import numpy as np

class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			currentsum = 0
		else:
			currentsum = 1 / n
			for i in range(2, n):
				currentsum = currentsum + currentsum / (n - i + 1)
		return 1 - currentsum


class Solution:

	def nthPersonGetsNthSeat(self, n: int) -> float:
		if n == 1:
			return 1
		pick = [1] + [0] * (n - 2) + [1]
		prob = 0
		for i in range(n - 2, 0, -1):
			left = n - i
			pick[i] = 1 / left + (left - 2) / left * pick[i + 1]
			prob += pick[i]
		return (prob + 1) / n