这100个人分别拿到了从1号到100号的座位，这些乘客会按号码顺序登机并对号入座，如果他们发现对应号座位被别人坐了，就会在剩下空的座位随便挑一个坐．现在假设1号乘客不记得自己的座位，他会在100个座位中随便选一个座位坐下，问：第100人正确坐到自己坐位的概率是多少？

面试中遇到了这道题，我的想法

设P(k)是总共k个人时第k个人坐到自己座位的概率，那么100个人时概率如下

若第1个人坐到自己位置上，第100个人肯定可以坐到自己座位，若第1个人坐到第100个人座位上，那么第100个人坐到自己位置的概率为0，若第1个人坐到第i个人的位置，那么第2到i-1个位置的人都不会坐错，第i个人选择时与第一个人情况相同，若坐到第1个人的位置上，第100个人肯定可以坐到自己座位，因此后续子问题相当于总共i个人时第i个人可以坐到自己位置上的概率。

但是当我推出这个式子时感到内心还是崩溃的，这感觉是一个动态规划问题递归求解..如何能笔算出答案呢.. 此时我想到了如果从反向看是否能有所突破

设Q(k)是总共k个人时第k个人不能坐到自己座位的概率，那么100个人时概率如下

若第1个人坐到第100个人位置上，第100个人肯定坐不到自己座位，若第1个人坐到自己座位，那么第100个人坐不到自己位置概率是0，若第1个人坐到第i个人的位置上，那么第2到第i-1个人不会坐错，第i个人选择时与第一个人情况相同，若坐到第1个人位置上，第100个人坐不到自己位置概率是0，坐到第100个人的位置上，第100个人肯定坐不到自己座位，因此问题分解和P的假设形式一样但是代表意义不同。

两个表达式初值方面，P(2)与Q(2)的概率均为1/2，P(k)与Q(k)有以下统一形式

那么P(100)与Q(100)的值也应该相同，而P(100)+Q(100)=1，所以问题答案是1/2