python 爬楼梯（lintcode）

描述：

爬楼梯
原题地址：http://www.lintcode.com/zh-cn/problem/climbing-stairs/
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例

比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法
返回 3

思路

这道题本质上就是一道斐波那契数列的应用
假设一共有10阶楼梯，每步可以爬1步或者2步，那么你爬到10阶一共有两种方法，从8阶爬2步，或从9阶爬1步，那么爬到9阶也是这样，那这就是一共基本的斐波那契数列。

代码

class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def climbStairs(self, n):
        # write your code here
        f = [0, 1]
        for i in range(2, n+2):
            f.append(f[i-1] + f[i-2])
        return f[n+1]

递归算法

def fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

学习

ted斐波那契数列：http://open.163.com/movie/2014/2/N/O/M9HKRT25D_M9HNA0UNO.html
还有一种快速求幂法：http://blog.csdn.net/qmickecs/article/details/70405354