今天的题目是1227. Airplane Seat Assignment Probability。

比较简单的题目，我的思路大概是这样的。

先假设f(n)为有 n 个人时，第 n 个人坐到自己位置的概率。

首先，第 1 个人随机选位置的时候，可能有三种情况：

1. 选到了自己的位置，那么后面就不会有人发现自己座位被做了，此时第 n 个人一定会坐到自己的位置。
2. 选到了第 n 个人的位置，这时第 n 个人就会坐到第 1 个人的位置上。
3. 选到了第 k 个人位置，这时，第 k 个人前面的（除了第一个人）都坐到了自己的位置，直到第 k 个人时，问题转化求解f(n-k+1)。

因此，我们可以列出下面的递推公式：

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \ \frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) &, & n!=1 \end{aligned} \right. $$

对第二个公式进一步化简得到：

$$ \begin{aligned} f(n) = & \frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) \ = & \frac 1 n (f(1) + \sum_{k=2}^{n-1}f(k)) \ = & \frac{1}{n} \sum_{k=1}^{n-1}f(k) \end{aligned} $$

因此递推公式可以写成：

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \ \frac{1}{n} \sum_{k=1}^{n-1}f(k) &, & n!=1 \end{aligned} \right. $$

根据递推公式可以写出如下代码：

1
double nthPersonGetsNthSeat(int n) {
2
  double sum = 1.0;
3
  for(int k = 2;k <= n;k++) {
4
    res = sum / k;
5
    sum += res;
6
  }
7
  return res;
8
}

我们将一些值代入到公式中可以发现这样一个事情：

$$ \begin{aligned} f(2) & = \frac{1}{2} f(1) \ f(3) & = \frac{1}{3} (f(1) + f(2)) = \frac{1}{2} f(1) \ … & \ f(n) & = \frac{1}{n} (f(1) + f(2) + … + f(n-1) ) \ & = \frac{1}{n} (f(1) + \frac{1}{2}f(1) + … + \frac{1}{2}f(1)) \ & = \frac{1}{n} (f(1) + \frac{n-2}{2}f(1)) \ & = \frac{1}{2} f(1) \end{aligned} $$

因此递推公式进一步简化成：

$$ f(n) = \left{ \begin{aligned} 1.0 &, & n == 1 \ \frac{1}{2} f(1) &, & n!=1 \end{aligned} \right. $$

因此，代码如下：

1
double nthPersonGetsNthSeat(int n) {
2
  return n > 1 ? 0.5 : 1.0;
3
}