拒绝懒惰的家

需求:

有一个台阶数为N的楼梯,可以有两种等楼梯的方法:一次上一阶,或者一次上两阶.问对于N阶楼梯,共有多少种不同的上法?
如:
N=1:  1种
N=3:  3种(1+1+1, 1+2, 2+1)
N=4:  5种(1+1+1+1, 1+2+1, 1+1+2, ,2+1+1, 2+2)

算法:

1.这个题目咋一看似乎是数的拆分问题的一种,可以用解决拆分问题的方法来解决.

2.比较简单的方法是递推求解:
设Y为台阶数为N时,上楼梯的方法数.则:
N=1, Y=1
N=2, Y=2
N=3, Y=3
N=4, Y=5
N=5, Y=8
......
如果仔细观察Y值,可以发现满足Fibonacci数列.可是我不会证明,记得以前我们高中老师证明过一次,可是当时就没有看懂.
如果这样,解法就相当简单了.
def Stairways(N):
    a,b=0,1
    for i in xrange(n):
        a,b=b,a+b
    return b

讨论:

如果题目要求打印出所有的方法步骤,还是使用拆分发比较好.