package main;

/**
 * 有 n 位乘客即將登機(jī)，飛機(jī)正好有 n 個(gè)座位。第一位乘客的票丟了，他隨便選了一個(gè)座位坐下。
 *
 * 剩下的乘客將會(huì)：
 *
 * 如果他們自己的座位還空著，就坐到自己的座位上，
 *
 * 當(dāng)他們自己的座位被占用時(shí)，隨機(jī)選擇其他座位
 * 第 n 位乘客坐在自己的座位上的概率是多少？
 *
 *  
 *
 * 示例 1：
 *
 * 輸入：n = 1
 * 輸出：1.00000
 * 解釋：第一個(gè)人只會(huì)坐在自己的位置上。
 * 示例 2：
 *
 * 輸入: n = 2
 * 輸出: 0.50000
 * 解釋：在第一個(gè)人選好座位坐下后，第二個(gè)人坐在自己的座位上的概率是 0.5。
 *  
 *
 * 提示：
 *
 * 1 <= n <= 10^5
 *
 * 來源：力扣（LeetCode）
 * 鏈接：https://leetcode-cn.com/problems/airplane-seat-assignment-probability
 * 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
 */
public class AirplaneSeatAssignmentProbability {

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

  private static double ownSeat(int n) {
    //1、判斷是否滿足動(dòng)態(tài)規(guī)劃
    //2、確定子問題參數(shù)、界定和計(jì)算順序
    //概率問題取反，求1-最后一個(gè)人位置被占用的概率。輸入n
    //3、初始值以及追蹤數(shù)組以及遞推函數(shù)
    if (n==1) return 1;
    if (n==2) return 0.5;
    double[] dp = new double[n];
    dp[0]=1;
    dp[1]=0.5;
    //找規(guī)律（求第n個(gè)人座位被占用概率）
    //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

    //結(jié)論：a、一下子占用n 概率至少1/3 b、1若占用自己，必然不會(huì)占用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]);//化簡以后發(fā)現(xiàn)除1外一直0.5
    }

    return 1-dp[n-1];


  }

}