我叫关小破，是一个轻微幻听症患者。
今天上午9点15分，收到女友瑾儿发来的语音，她约我到LTG咖啡馆见面，说是要带我去一家新开的心境诊所，名字听上去很像是看心理或者精神问题的。
女朋友定的这家咖啡馆很是难找，问了3个人，才在一个巷子深处找到它。这个巷子很长，很乱，很嘈杂，各式各样的店铺很多，没有一般咖啡馆周围环境的那种清幽。
电线杆上的电子牌显示着：LTG咖啡馆，左面楼梯直上三楼。现在是11点44分，离女朋友约定的时间还有16分钟，我看到了这个楼梯。“我靠，好长”，狭长的棕色木质楼梯，意乱情迷的五彩灯光，墙上贴满了金属朋克风的装饰画，唯一煞风景的就是台阶上贴的租房和各式神医小卡片。
楼梯口旁边有个牌子上用粉笔楷体字写着：此楼梯一共五十阶，为远离尘世烦恼，台阶稍高，来者量力而行，每次一阶或者两阶。我试了试，三阶确实有点扯。估计每个来的人都会像我这样扯一次。就这样，我有时一阶，有时两阶。快到楼梯尽头时，从上面走下来一个胡子比头发还浓密，带着黑色圆框眼睛的中年人，这个资源没得到合理配置的男人突然站住。他真的很客气，离我还有九个台阶就侧身示意我先过，当然我也比较有修养，我不禁三步并做两步，也顾不得当下的扯与不扯。
“不急，小伙子，我来这里很多次了，我每次上台阶都不会和以前走的一样，另外我怕扯，每次都是一阶或者两阶，今天是我最后一次来这里，你能告诉我，我来这里多少次了吗”。听到这里，我停了下来倚在墙上，这个中年人慢慢走向我，一股浓浓的酒精味扑面而来。他游离的眼神中带着满满的期许不断的打量着我，我在脑海中快速总结了一下他心中的疑惑。
“50级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，共有多少种走法”
此刻是11点50分，暴力可以解决问题，但是与这个楼梯的独特气质不符，主要是10分钟可能得不出中年男人想要的结果，从而让一个女人理直气壮的爆发。
++++++++正儿八经的分割线++++++++
动态规划：大事化小，小事化了。
动态规划是一种解决问题的方法，通过将问题分解为子问题，并总结关系，得到解决问题的思路。
问题分析：逆向思维
令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)这样的表达式称为这个问题的状态转移方程；50,49……3,2这样的数字可以看成问题的状态。
Python3实现
#递归实现
def Floor_Recursion(number):
if number==1:#边界条件
return 1
if number==2:#边界条件
return 2
return Floor_Recursion(number-1)+Floor_Recursion(number-2)#状态转移方程
递归实现简单，但是容易造成栈溢出。分析其原因，是因为上面的程序调用了太多重复的结果，因此需要优化。一种方法被称为备忘录，就是把需要程序用到的结果储存起来，例如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]#状态转移方程
return memo[number]
还有一种方法称为动态规划，这需要仔细分析问题的状态转移方程。以本问题为例，每一个状态只是和之前的2个状态有关。因此实际上只需要存储2个结果。
#动态规划
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]#等同于状态转移方程
count+=1
return result[-1]
print(Floor_DP(50))
#结果：20365011074
++++++++嬉皮笑脸的分割线++++++++
看着屏幕上出现的结果，两百……，我不由得一怒。这胡瓢瓢是在逗我吗。看来我得使用暴力了。空气中只是弥漫着淡淡的酒精味，胡瓢瓢已不见了踪影。12点00分了，忍着扯痛，赶紧迈上去。
来到了咖啡馆的门口，大大的LTG霓虹灯闪烁，布鲁斯蓝调音乐时隐时现，门上挂个牌子写着：方便人流，只进不出。看着人流两字，不由得一哆嗦以为到了黑诊所。推开门，里面还真看不出是个咖啡馆，没有多少咖啡的香气，倒是酒精的气味更浓烈。
“这是LTG咖啡店吗”
“是的，先生，请问您需要什么”
“你们这里怎么这么大的酒精味啊”
“哦，先生，咖啡馆在里面的，这外面是酒吧，外面消愁，里面寻欢”
“我其实是来消愁的，我可以做里面吗”
“里面不允许喝酒的，先生”
“我不点酒”
“先生，您需要点点什么”
“这个门写着只进不出，为什么刚才有个人出去了”
“刚才吗，那个人是我们老板。先生，请问您需要什么”
“两杯热果汁”
“先生，您有现金吗，34，我们这里的付钱二维码需要升级，老板暂时不让用了，因为我们老板是聋哑人，以后每一笔通过二维码的消费，都会向聋哑人基金会自动捐款。”
“先生，您没事吧”
“哦，哦，我没事，我有现金，给”
我拿着两杯果汁，穿过充斥着酒话、沉闷的外屋，进了里屋。里屋很安静，是很小的一个咖啡馆，复古仿欧式的装潢，还掺杂一些地中海式的装饰，《Five Hundred Miles》的声音可以直达人心。我四处张望，寻找我的女朋友。
“破罐子，我在着呢”
我循着声音向身后望去，女朋友瑾儿正在一个角落里，笑的很开心。
“瑾儿，我好像有些加重了，你说的那个新开的叫什么心境的诊所，怎么样啊”
“什么诊所啊，什么怎么样啊，我没和你说过啊”
“你今天早上发语音和我说的啊，你不信自己听”，我掏出手机，却不敢摁下那段语音的重放。
“哈哈，傻罐子，我逗你的”
“只有一句话，你不用担心会是幻听，那就是我爱你，破罐子。因为你每一次听到，都是我真实的在说”
“LTG，这个名字什么意思啊，挺有创意的啊，我觉得是三个对老板特别有意义的首写字母，你说会不会是老板的女朋友的名字缩写啊”
“我不这么认为，我觉得像是楼梯高的缩写，哈哈”
