我叫關小破，是一個輕微幻聽癥患者。
今天上午9點15分，收到女友瑾兒發(fā)來的語音，她約我到LTG咖啡館見面，說是要帶我去一家新開的心境診所，名字聽上去很像是看心理或者精神問題的。
女朋友定的這家咖啡館很是難找，問了3個人，才在一個巷子深處找到它。這個巷子很長，很亂，很嘈雜，各式各樣的店鋪很多，沒有一般咖啡館周圍環(huán)境的那種清幽。
電線桿上的電子牌顯示著：LTG咖啡館，左面樓梯直上三樓?，F(xiàn)在是11點44分，離女朋友約定的時間還有16分鐘，我看到了這個樓梯?！拔铱?，好長”，狹長的棕色木質樓梯，意亂情迷的五彩燈光，墻上貼滿了金屬朋克風的裝飾畫，唯一煞風景的就是臺階上貼的租房和各式神醫(yī)小卡片。
樓梯口旁邊有個牌子上用粉筆楷體字寫著：此樓梯一共五十階，為遠離塵世煩惱，臺階稍高，來者量力而行，每次一階或者兩階。我試了試，三階確實有點扯。估計每個來的人都會像我這樣扯一次。就這樣，我有時一階，有時兩階?？斓綐翘荼M頭時，從上面走下來一個胡子比頭發(fā)還濃密，帶著黑色圓框眼睛的中年人，這個資源沒得到合理配置的男人突然站住。他真的很客氣，離我還有九個臺階就側身示意我先過，當然我也比較有修養(yǎng)，我不禁三步并做兩步，也顧不得當下的扯與不扯。
“不急，小伙子，我來這里很多次了，我每次上臺階都不會和以前走的一樣，另外我怕扯，每次都是一階或者兩階，今天是我最后一次來這里，你能告訴我，我來這里多少次了嗎”。聽到這里，我停了下來倚在墻上，這個中年人慢慢走向我，一股濃濃的酒精味撲面而來。他游離的眼神中帶著滿滿的期許不斷的打量著我，我在腦海中快速總結了一下他心中的疑惑。
“50級臺階的樓梯，從下往上走，每跨一步只能向上1級或者2級臺階，共有多少種走法”
此刻是11點50分，暴力可以解決問題，但是與這個樓梯的獨特氣質不符，主要是10分鐘可能得不出中年男人想要的結果，從而讓一個女人理直氣壯的爆發(fā)。
++++++++正兒八經(jīng)的分割線++++++++
動態(tài)規(guī)劃：大事化小，小事化了。
動態(tài)規(guī)劃是一種解決問題的方法，通過將問題分解為子問題，并總結關系，得到解決問題的思路。
問題分析：逆向思維
令T(50)表示所有的走法。當我站在50級臺階的時候，我要么是從49級臺階走了1階上來的，要么是從48階臺階走了2階上來的。因此T(50)=T(49)+T(48)，同理可推得T(49)=T(48)+T(47)、T(49)=T(48)+T(47)……T(3)=T(2)+T(1)、T(2)=2、T(1)=1。這樣就把原來的求T(50)的問題，轉換為求T(49)、T(48)………T(3)這樣的子問題。T(2)=2、T(1)=1稱為這個問題的邊界條件，試想如果沒有邊界條件，就會分解為無限個子問題，因此得不到問題的解。類似T(50)=T(49)+T(48)這樣的表達式稱為這個問題的狀態(tài)轉移方程；50,49……3,2這樣的數(shù)字可以看成問題的狀態(tài)。
Python3實現(xiàn)
#遞歸實現(xiàn)
def Floor_Recursion(number):
if number==1:#邊界條件
return 1
if number==2:#邊界條件
return 2
return Floor_Recursion(number-1)+Floor_Recursion(number-2)#狀態(tài)轉移方程
遞歸實現(xiàn)簡單，但是容易造成棧溢出。分析其原因，是因為上面的程序調用了太多重復的結果，因此需要優(yōu)化。一種方法被稱為備忘錄，就是把需要程序用到的結果儲存起來，例如Python的字典存儲。
#備忘錄
def Floor_Memo(number):
memo={1:1,2:2}#邊界條件
count=2
while count<number:
count+=1
memo[count]=memo[count-1]+memo[count-2]#狀態(tài)轉移方程
return memo[number]
還有一種方法稱為動態(tài)規(guī)劃，這需要仔細分析問題的狀態(tài)轉移方程。以本問題為例，每一個狀態(tài)只是和之前的2個狀態(tài)有關。因此實際上只需要存儲2個結果。
#動態(tài)規(guī)劃
def Floor_DP(number):
if number==1:#邊界條件
return 1
if number==2:#邊界條件
return 2
result=[1,2]#只存儲前2次結果
count=2
while count<number:
nexta=sum(result)
result=[result[1],nexta]#等同于狀態(tài)轉移方程
count+=1
return result[-1]
print(Floor_DP(50))
#結果：20365011074
++++++++嬉皮笑臉的分割線++++++++
看著屏幕上出現(xiàn)的結果，兩百……，我不由得一怒。這胡瓢瓢是在逗我嗎?？磥砦业檬褂帽┝α??？諝庵兄皇菑浡木凭?，胡瓢瓢已不見了蹤影。12點00分了，忍著扯痛，趕緊邁上去。
來到了咖啡館的門口，大大的LTG霓虹燈閃爍，布魯斯藍調音樂時隱時現(xiàn)，門上掛個牌子寫著：方便人流，只進不出?？粗肆鲀勺郑挥傻靡欢哙乱詾榈搅撕谠\所。推開門，里面還真看不出是個咖啡館，沒有多少咖啡的香氣，倒是酒精的氣味更濃烈。
“這是LTG咖啡店嗎”
“是的，先生，請問您需要什么”
“你們這里怎么這么大的酒精味啊”
“哦，先生，咖啡館在里面的，這外面是酒吧，外面消愁，里面尋歡”
“我其實是來消愁的，我可以做里面嗎”
“里面不允許喝酒的，先生”
“我不點酒”
“先生，您需要點點什么”
“這個門寫著只進不出，為什么剛才有個人出去了”
“剛才嗎，那個人是我們老板。先生，請問您需要什么”
“兩杯熱果汁”
“先生，您有現(xiàn)金嗎，34，我們這里的付錢二維碼需要升級，老板暫時不讓用了，因為我們老板是聾啞人，以后每一筆通過二維碼的消費，都會向聾啞人基金會自動捐款?！?br>
“先生，您沒事吧”
“哦，哦，我沒事，我有現(xiàn)金，給”
我拿著兩杯果汁，穿過充斥著酒話、沉悶的外屋，進了里屋。里屋很安靜，是很小的一個咖啡館，復古仿歐式的裝潢，還摻雜一些地中海式的裝飾，《Five Hundred Miles》的聲音可以直達人心。我四處張望，尋找我的女朋友。
“破罐子，我在著呢”
我循著聲音向身后望去，女朋友瑾兒正在一個角落里，笑的很開心。
“瑾兒，我好像有些加重了，你說的那個新開的叫什么心境的診所，怎么樣啊”
“什么診所啊，什么怎么樣啊，我沒和你說過啊”
“你今天早上發(fā)語音和我說的啊，你不信自己聽”，我掏出手機，卻不敢摁下那段語音的重放。
“哈哈，傻罐子，我逗你的”
“只有一句話，你不用擔心會是幻聽，那就是我愛你，破罐子。因為你每一次聽到，都是我真實的在說”
“LTG，這個名字什么意思啊，挺有創(chuàng)意的啊，我覺得是三個對老板特別有意義的首寫字母，你說會不會是老板的女朋友的名字縮寫啊”
“我不這么認為，我覺得像是樓梯高的縮寫，哈哈”
