# coding:utf-8

# 【题目1】

# 斐波那契数列 又称黄金分割数列，指的是这样的一个数列 1,1,2,3,5,8,13,21,,,

# 这个数列从第三项开始，每一项都等于签名的2项和，求数列的第n项

def memo(func):

    cashe={}

    def wrap(*args):

        if args not in cashe:

            cashe[args]=func(*args)

        return cashe[args]

    return wrap

@memo

def fi(n):

    if n<=1:

        return 1

    return fi(n-1) + fi(n-2)

# print fi(5)

# 【题目2】

# 一个共有10个台阶的楼梯，从下面走到上面，一次只能迈1-3个台阶，并且不能后退，走完所有的台阶共有多少种方法

当有n个台阶时，在上n台阶之前一步，如果是一次上三个台阶 就有f(n-3)中方法 如果一次上2个台阶就有f(n-2)中方法，如果一次上1个台阶剩下的就有f(n-1)种方法

n=1时 c=1

n=2 c=2

n=3 c=4

n=4

 (1)第一步迈1个台阶 剩下3步 f（n-1）=f（3）=4

（2）第一步迈2个台阶 剩下2步 f（n-2）=f（2）=2

（3）第一步迈3个台阶 剩下1步 f（n-3）=f（1）=1

c=f(n-3)+f(n-2)+f(n-1)

......

@memo

def climb(n,steps):

    count=0

    if n==0:

        count=1

    elif n>0:

        for step in steps:

            count+=climb(n-step,steps)

    return count

@memo

def climb2(n):

    count=0

    if n<=1:

        count=1

    elif n==2:

        count=2

    elif n>2:

        count=climb2(n-1)+climb2(n-2)+climb2(n-3)

    return count

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

print  climb2(10)