算法 青蛙跳台阶

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

输入格式:
首先输入数字n，代表接下来有n组输入，50>=n>=0,然后每行一个数字，代表台阶数，数字为小于60的整数

输出格式:
对每一组输入，输出青蛙的跳法。

输入样例:
3
1
2
3
输出样例:
1
2
3

用斐波那契数列解决。
直接用递归会超时，所以用list将前面计算过的数值保存下来。这样后面需要计算时直接取值就可以了。

def fun(n):
    if li[n] != 0:
        return li[n]
    else:
        li[n] = fun(n-1) + fun(n-2)
        return li[n]

if __name__ == "__main__":
    li = [0 for n in range(10001)]
    li[0] = 0
    li[1] = 1
    li[2] = 2
    n=0
    n = int(input())
    for i in  range(n):
        num = int(input())
        print(fun(num))

CDSN有一个大佬写了斐波那契数列的算法和相应的性能测试： Python中斐波那契数列的四种写法