LeetCode 1227. 飞机座位分配概率（DP+数学归纳法）

示例 1：
输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
 
提示：
1 <= n <= 10^5

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        double fn = 1.0, sum_f_i = 1.0;
        for (int i = 2; i <= n; ++i) {
            fn = 1 - sum_f_i/i;
            sum_f_i += fn;
        }
        return fn;
    }
};

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