爬楼梯（记忆化递归算法）

爬楼梯（记忆化递归算法）

假设你正在爬楼梯。需要 n?阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

要求：使用记忆化递归算法设计程序

示例1：

输入：0

输出：1

解释：有一种方法可以爬到楼顶。

1、0阶

示例2：

输入：2

输出：2

解释：有两种方法可以爬到楼顶。

1、1 阶 + 1 阶

2、2 阶

示例3：

输入：3

输出：3

解释：有三种方法可以爬到楼顶。

1、1 阶 + 1 阶 + 1 阶

2、1 阶 + 2 阶

3、2 阶 + 1 阶

def climbStairsMemo(n,memo):
    if memo[n]>0:
        return memo[n]
    else:
        if n==1:
            memo[n]=1
        elif n==2:
            memo[n]=2
        else:
            memo[n]=climbStairsMemo(n-1,memo)+climbStairsMemo(n-2,memo)
        return memo[n]
def climbStairs(n):
    memo=[0 for i in range(n+1)]
    return climbStairsMemo(n,memo)
n = eval(input())
print(climbStairs(n))