# coding:utf8

''' v1 '''


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


print fib(10)

''' v2 '''


def fib1(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return 1
    cache[n] = fib1(n - 1, cache) + fib1(n - 2, cache)
    return cache[n]


print fib1(999)

''' v3 '''


# coding:utf8
def memo(func):
    cache = {}

    def wrapp(*args, **kwargs):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapp


# 语法糖实现 等价于fib=memo(fib)
@memo
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)


# fib=memo(fib)
print fib(10)

#coding:utf8
def memo(func):
    cache = {}

    def wrapp(*args, **kwargs):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapp


# 语法糖实现 等价于climb = memo(climb)
@memo
def climb(n, steps=None):
    count = 0
    if n == 0:
        count = 1
    elif n >0:
        for step in steps:
            count += climb(n - step, steps)
    return count

print climb(195,(1,2,3))