這100個(gè)人分別拿到了從1號(hào)到100號(hào)的座位，這些乘客會(huì)按號(hào)碼順序登機(jī)并對(duì)號(hào)入座，如果他們發(fā)現(xiàn)對(duì)應(yīng)號(hào)座位被別人坐了，就會(huì)在剩下空的座位隨便挑一個(gè)坐．現(xiàn)在假設(shè)1號(hào)乘客不記得自己的座位，他會(huì)在100個(gè)座位中隨便選一個(gè)座位坐下，問(wèn)：第100人正確坐到自己坐位的概率是多少？

面試中遇到了這道題，我的想法

設(shè)P(k)是總共k個(gè)人時(shí)第k個(gè)人坐到自己座位的概率，那么100個(gè)人時(shí)概率如下

若第1個(gè)人坐到自己位置上，第100個(gè)人肯定可以坐到自己座位，若第1個(gè)人坐到第100個(gè)人座位上，那么第100個(gè)人坐到自己位置的概率為0，若第1個(gè)人坐到第i個(gè)人的位置，那么第2到i-1個(gè)位置的人都不會(huì)坐錯(cuò)，第i個(gè)人選擇時(shí)與第一個(gè)人情況相同，若坐到第1個(gè)人的位置上，第100個(gè)人肯定可以坐到自己座位，因此后續(xù)子問(wèn)題相當(dāng)于總共i個(gè)人時(shí)第i個(gè)人可以坐到自己位置上的概率。

但是當(dāng)我推出這個(gè)式子時(shí)感到內(nèi)心還是崩潰的，這感覺(jué)是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題遞歸求解..如何能筆算出答案呢.. 此時(shí)我想到了如果從反向看是否能有所突破

設(shè)Q(k)是總共k個(gè)人時(shí)第k個(gè)人不能坐到自己座位的概率，那么100個(gè)人時(shí)概率如下

若第1個(gè)人坐到第100個(gè)人位置上，第100個(gè)人肯定坐不到自己座位，若第1個(gè)人坐到自己座位，那么第100個(gè)人坐不到自己位置概率是0，若第1個(gè)人坐到第i個(gè)人的位置上，那么第2到第i-1個(gè)人不會(huì)坐錯(cuò)，第i個(gè)人選擇時(shí)與第一個(gè)人情況相同，若坐到第1個(gè)人位置上，第100個(gè)人坐不到自己位置概率是0，坐到第100個(gè)人的位置上，第100個(gè)人肯定坐不到自己座位，因此問(wèn)題分解和P的假設(shè)形式一樣但是代表意義不同。

兩個(gè)表達(dá)式初值方面，P(2)與Q(2)的概率均為1/2，P(k)與Q(k)有以下統(tǒng)一形式

那么P(100)與Q(100)的值也應(yīng)該相同，而P(100)+Q(100)=1，所以問(wèn)題答案是1/2