解答牛顿爬楼梯问题

"""
一个人一次可以迈过一节楼梯, 或者两节楼梯
问 N节楼梯有多少种走法?
分析: 
1节楼梯有1种走法
2节楼梯有2种走法

3节楼梯的走法数量 = 2节楼梯的走法数量(最后一次走一步的数量) + 1节楼梯的走法数量(最后一次走两步的数量)
N节楼梯的走法数量 = N-1 节楼梯的走法数量 + N-2节楼梯的走法数量

f(N) = f(N-1) + f(N-2)

"""

def take_1_2_stairs(N):

    if N == 1:
        return 1

    if N == 2:
        return 2

    return take_1_2_stairs(N-1) + take_1_2_stairs(N-2)


"""
f(N) = f(N-1) + f(N-2) + f(N-3)
"""
# 如果最多能迈三节
def take_1_2_3_stairs(N):
    if N == 1:
        return 1
    if N == 2:
        return 2
    if N == 3:
        return 4

    return take_1_2_3_stairs(N-1) + take_1_2_3_stairs(N-2) + take_1_2_3_stairs(N-3)


def main():
    result_1_2 = take_1_2_stairs(10)
    result_1_2_3 = take_1_2_3_stairs(10)
    print("如果每次迈出1-2个台阶, 共有",result_1_2, "种解法")
    print("如果每次迈出1-3个台阶,共有", result_1_2_3, "种走法")

if __name__ == '__main__':
    main()