简单的楼梯问题

| Comments

问题描述

有个楼梯,一个人一次可以走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

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

Comments