问题描述

有个楼梯，一个人一次可以走1级或2级，那么走上一条100级的楼梯，有多少种不同的走法?

找到规律

先找到规律，从简单情况开始，设f(n)是n级楼梯的走法数量。那么就有:

1. n=1,肯定只有一种走法,即f(1)=1
2. n=2,可以一级级走或者一次两级,即f(2)=2
3. 对于n>2的情况，如果第一次走1级，剩下的楼梯有f(n-1)种走法，如果走2级，剩下的楼梯有f(n-2)种走法。 那么总的走法是f(n)=f(n-1)+f(n-2)。

斐波纳契数列

说白了，这是个斐波纳契数列。计算的时候简单的动态规划即可。下面是简单的ruby源码:

a,b=1,2
98.times {b,a=a+b,b}
p b #=> 573147844013817084101

看，真的是一个天文数字来的。