Saved from https://leetcode.com/problems/airplane-seat-assignment-probability/

lc1227

class Solution {
    // f(n) = 1 / n + (n - 2) / n * f(n - 1)
    // 
    // f(n) = 1/n                                    -> 1st person picks his own seat
    //      + 1/n * 0                                 -> 1st person picks last one's seat
    //	    + (n-2)/n * (                            ->1st person picks one of seat from 2nd to (n-1)th
    //	      1/(n-2) * f(n-1)                   -> 1st person pick 2nd's seat
    //	      1/(n-2) * f(n-2)                  -> 1st person pick 3rd's seat
    //        ......
    //        1/(n-2) * f(2)                     -> 1st person pick (n-1)th's seat
	//        )
    // 
    //      => f(n) = 1/n * ( f(n-1) + f(n-2) + f(n-3) + ... + f(1) )

    //  Now, you can easily get
    //  f(1) = 1
    //  f(2) = 1/2
    //  f(3) = 1/2
    //  ...    
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0d : .5d;
    }
    
    public double nthPersonGetsNthSeat_naive(int n) {
        if (n == 1) return 1.0d;
        return 1d / n + (n - 2d) / n * nthPersonGetsNthSeat(n - 1);
    }
}