1227. Airplane Seat Assignment Probability

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

这个题目推导公式是这样的:假设N个人的概率是f(N)的话,考虑f(N+1).

  1. 第一个人如果占据1th位置,那么概率是1.0
  2. 如果占据2th位置的话,那么2号人可以看做是1号人,此时概率是f(N)
  3. 。。。 如果占据nth位置的话,概率也是f(N)
  4. 所以f(N+1) = 1/n + (n-2)/n * f(N)
  5. 实际上f(N)=1/2,因为如果带入的话有f(N+1)=1/2. 它是一个常量

关于第二点可以看下面这个图

如果人员1使用作为2的时候
====================
座位:1 2 3 4 5 6
人员:  1
====================

1占据之后,实际情况变为
====================
座位:1 3 4 5 6
人员:2 3 4 5 6
====================

那么其实可以将2号人员认为就是1号人员(或者是1号座位编码变为2)

最后一步化简就看造化了。