package main;

/**
 * 有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
 *
 * 剩下的乘客将会：
 *
 * 如果他们自己的座位还空着，就坐到自己的座位上，
 *
 * 当他们自己的座位被占用时，随机选择其他座位
 * 第 n 位乘客坐在自己的座位上的概率是多少？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 1
 * 输出：1.00000
 * 解释：第一个人只会坐在自己的位置上。
 * 示例 2：
 *
 * 输入: n = 2
 * 输出: 0.50000
 * 解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
 *  
 *
 * 提示：
 *
 * 1 <= n <= 10^5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/airplane-seat-assignment-probability
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class AirplaneSeatAssignmentProbability {

  public static void main(String[] args) {
    System.out.println("最后一个人坐自己位置概率为："+ownSeat(4));
  }

  private static double ownSeat(int n) {
    //1、判断是否满足动态规划
    //2、确定子问题参数、界定和计算顺序
    //概率问题取反，求1-最后一个人位置被占用的概率。输入n
    //3、初始值以及追踪数组以及递推函数
    if (n==1) return 1;
    if (n==2) return 0.5;
    double[] dp = new double[n];
    dp[0]=1;
    dp[1]=0.5;
    //找规律（求第n个人座位被占用概率）
    //n=3  a、1占用3，2占用2，3占用1 1/3 ok
    // b、1占用自己，2占用自己，3占用自己 1/3 no
    // c、1占用2，2占用1，3占用自己 1/3*1/2 no
    // d、1占用2，2占用3，3占用1 1/3*1/2 ok
    // 占用概率 1-1/2=0.5

    //n=4  a、1占用4，2占用2，3占用3 4占用1 1/4 ok
    // b、1占用1，2占用2，3占用3 4占用4 1/4 no
    // c、1占用2，2占用1，3占用3 4占用4 1/4*1/3 no
    // d、1占用2，2占用3，3占用1 4占用4 1/4*1/3*1/2 no
    // e、1占用2，2占用4，3占用3 4占用1 1/4*1/3 ok
    // f、1占用2，2占用3，3占用4 4占用1 1/4*1/3*1/2 ok
    // f、1占用3，2占用2，3占用1 4占用4 1/4*1/2 no
    // f、1占用3，2占用2，3占用4 4占用1 1/4*1/2 ok
    // 占用概率 1-1/4-1/4*1/3-1/4*1/3*1/2-1/4*1/2=0.5

    //结论：a、一下子占用n 概率至少1/3 b、1若占用自己，必然不会占用n c、1若占用其他位置，则子问题抛给其他人开始
    //1/n*(历代相加)
    for (int i = 3; i <= n; i++) {
      dp[i-1]=1.0/i*(dp[i-2]*(i-1)+dp[i-2]);//化简以后发现除1外一直0.5
    }

    return 1-dp[n-1];


  }

}