python面试之python实现楼梯问题

python实现楼梯问题

有一段连续的楼梯，共10阶台阶。芬琦要从楼梯底部向上爬到楼梯顶部。
她可以一次迈一阶台阶，也可以一次迈两阶台阶（但绝对不会向下退回）。
比如她每次都迈一阶台阶，十次可以爬到顶部，这算作一种爬楼梯方式，
我们可以把它记作（1，1，1，1，1，1，1，1，1，1）；
她也可以每次都迈两阶台阶，这也算作一种爬楼梯方式，可记作（2，2，2，2，2）；
当然还有很多种爬楼梯方式，比如（1，2，2，1，1，2，1）。
问她一共有多少种不同的爬楼梯方式?

台阶：0 1 2 3
方式：0 1 2 (1->2 2->1)

def walk(x):
    if x==0:
        return 0
    elif x==1:
        return 1
    elif x==2:
        return 2
    else:
        return walk(x-1)+walk(x-2)

print(walk(10))