題目
有個(gè)人想上一個(gè)50級(jí)的臺(tái)階巾兆，每次只能邁1級(jí)或者邁2級(jí)臺(tái)階如捅，問(wèn)：這個(gè)人有多少種方法可以把臺(tái)階走完？例如：總共3級(jí)臺(tái)階样傍，可以先邁1級(jí)再邁2級(jí)横缔，或者先邁2級(jí)再邁1級(jí)，或者邁3次1級(jí)總共3中方式衫哥。
心路歷程
這個(gè)題目我剛看到的時(shí)候覺得很有意思茎刚，值得思考一下，也和同學(xué)討論過(guò)思路撤逢，并沒有直接去網(wǎng)上找答案膛锭，覺得那樣的話就浪費(fèi)了捌斧，所以自己先嘗試著解了。
說(shuō)這么多是希望大家也不要直接去看解答泉沾，因?yàn)榭赐曛笠粋€(gè)星期也就忘了捞蚂。可以先收藏一手跷究，自己去試試然后再回來(lái)看姓迅，我會(huì)把我自己解的思路和正解都放在這篇文章里。
思路step1：
從初中生的思路來(lái)看俊马，第一個(gè)能想到的方法肯定是一個(gè)二元方程丁存，也就是x+2y=50，其中x代表邁1步柴我，y代表邁2步解寝，無(wú)論怎么邁總共50級(jí)臺(tái)階。
接下來(lái)的問(wèn)題就是求這個(gè)方程解的數(shù)量（不是某一個(gè)解）艘儒，x+2y-50=0這個(gè)方程的所有解應(yīng)該是一條直線聋伦，所以我很單純的去把圖給畫了，就像下面這個(gè)樣子：
再考慮x和y都必須是整數(shù)才能符合題意界睁，y取值在025之間觉增，可以看出只要y是整數(shù)解那么x一定為整數(shù)解，0也可以作為一種特殊情況翻斟，綜上y可能的取值是：025共26個(gè)逾礁。那么相對(duì)應(yīng)的x取值也就可以算出來(lái)了。
這里還有一種情況访惜，如果總臺(tái)階數(shù)不是50嘹履，那么y的取值范圍有可能是0~24.5，那么我認(rèn)為y只能取值到24债热，也就是向下取整砾嫉。
思路step2：
如果僅從數(shù)量上來(lái)看，xy總共有26種組合的方式阳柔，但這肯定不是最后答案焰枢，例如蚓峦，邁2次1步再邁24次2步和先邁24次2步再邁2次1步是兩種不同的方式舌剂，那么接下來(lái)就是排列組合的問(wèn)題。
所以暑椰，我們要求的是所有xy同為整數(shù)的解的排列之和霍转，是不是感覺有點(diǎn)復(fù)雜了，但是沒關(guān)系一汽，前面說(shuō)的內(nèi)容都是用PHP可以實(shí)現(xiàn)的避消，排列組合也是可以用PHP實(shí)現(xiàn)的低滩。然后，排列組合算法的第一個(gè)問(wèn)題就是如何實(shí)現(xiàn)階乘岩喷？
在PHP中range函數(shù)可以建立一個(gè)包含指定范圍單元的數(shù)組恕沫，允許傳入三個(gè)參數(shù)起始值、終止值和步長(zhǎng)值纱意，例如rang(1,3)會(huì)返回包含1婶溯、2、3這三個(gè)數(shù)的一個(gè)數(shù)組偷霉。
另外PHP中的array_product函數(shù)可以計(jì)算數(shù)組中所有值的乘積迄委。
有了這兩個(gè)函數(shù)我們就可以自己寫出階乘的函數(shù)了，雖然我不知道效率怎么樣类少，但起碼我們不用往遞歸的方面去想了叙身，另外還需要考慮一下0和1階乘的情況，就是下面這個(gè)樣子：
有了階乘硫狞，排列也就有了：
回到問(wèn)題上來(lái)信轿，我們需要用到組合嗎？
首先残吩，總數(shù)量是確定的x+y虏两，而且第一次邁2步和后面無(wú)論第幾次邁2步都是相同的，所以這種排列組合其實(shí)可以轉(zhuǎn)化為“把雞蛋放入籃子”的問(wèn)題——將n個(gè)無(wú)差別的雞蛋放入m個(gè)籃子中共有幾種放法世剖。那么求組合數(shù)函數(shù)也是需要的：
接下來(lái)就是循環(huán)每一個(gè)可能解定罢，可以總是將x值作為雞蛋的數(shù)量，將xy之和作為籃子的數(shù)量旁瘫，也就是C(x+y,x)祖凫，舉個(gè)例子來(lái)說(shuō)就是，總共要邁26次腳酬凳，選擇其中2次只邁1步惠况，有多少種邁法。
思路step3：
有了前面那么多的思考宁仔，我們來(lái)寫代碼：
經(jīng)過(guò)測(cè)試稠屠，最終50級(jí)臺(tái)階的走法有20365011074種，二百零三億六千五百零一萬(wàn)一千零七十四種（醉了）翎苫。
那么到這里我就開始去網(wǎng)絡(luò)上找正確答案了权埠，讓我震驚了，發(fā)現(xiàn)我的思路果然是初中生的煎谍，且是從來(lái)不參加任何數(shù)學(xué)競(jìng)賽的那種攘蔽，下面我分析一下網(wǎng)絡(luò)上答案的思路。
答tu案cao
網(wǎng)上的解只有一種呐粘，那就是把這個(gè)問(wèn)題歸結(jié)為斐波那契數(shù)列的問(wèn)題满俗，完全看不出來(lái)好嗎转捕！
答案窮舉了總臺(tái)階數(shù)從1級(jí)到5級(jí)的情況，得出結(jié)論1級(jí)共1種走法唆垃，2級(jí)2種走法五芝，3級(jí)3中走法，4級(jí)5種走法辕万，5級(jí)有八種走法与柑，然后就開始研究斐波那契數(shù)列去了！
那你出個(gè)題目出個(gè)那么懸乎干嘛蓄坏！直接讓我們用PHP寫個(gè)斐波那契函數(shù)不就好了嗎价捧！要考察思維能力也得給點(diǎn)提示啊涡戳！比如說(shuō)設(shè)置兩個(gè)問(wèn)題：第一問(wèn)结蟋，當(dāng)臺(tái)階總數(shù)為5時(shí)有幾種走法？第二問(wèn)渔彰，當(dāng)臺(tái)階總數(shù)為n時(shí)有幾種走法嵌屎？
總之呢就是在面試的時(shí)候，如果你見過(guò)這題那么恭喜你恍涂，如果沒見過(guò)那么就可以去下一題了宝惰。
當(dāng)然也有大神給出了比較讓人信服的邏輯：
當(dāng)我們走到第50層的時(shí)候，最后有兩種選擇再沧，從49開始邁1級(jí)或者從48開始邁2級(jí)尼夺。那么到達(dá)50層的走法等于到達(dá)49層的走法+到達(dá)48層的走法，以此類推炒瘸，可以得到總的走法符合斐波那契數(shù)列淤堵，我們的代碼就好寫了。
恩............膜拜奧數(shù)大神的思維顷扩。
PHP寫斐波那契應(yīng)該是比較簡(jiǎn)單的問(wèn)題拐邪，那最后讓我們用答案中的斐波那契函數(shù)來(lái)驗(yàn)證一下自己的答案。
可以看到隘截，小編自己的思路和最終答案是相同的扎阶，只是過(guò)程相對(duì)復(fù)qing雜xi。
還是不太放心婶芭，測(cè)試了臺(tái)階總數(shù)從1~7的所有情況东臀，也都是符合答案的，甚至我沒有特殊考慮的只有1~2層的情況也能返回正確的答案雕擂。
