package main;

/**
 * 有 n 位乘客即將登機案腺，飛機正好有 n 個座位。第一位乘客的票丟了趁舀，他隨便選了一個座位坐下。
 *
 * 剩下的乘客將會：
 *
 * 如果他們自己的座位還空著挽荡，就坐到自己的座位上母剥，
 *
 * 當(dāng)他們自己的座位被占用時，隨機選擇其他座位
 * 第 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
 * 著作權(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("最后一個人坐自己位置概率為："+ownSeat(4));
  }

  private static double ownSeat(int n) {
    //1昙衅、判斷是否滿足動態(tài)規(guī)劃
    //2、確定子問題參數(shù)定鸟、界定和計算順序
    //概率問題取反绒尊，求1-最后一個人位置被占用的概率。輸入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個人座位被占用概率）
    //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若占用自己派敷，必然不會占用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];


  }

}