爬楼梯(记忆化递归算法)

2023-12-18 14:17:19

爬楼梯(记忆化递归算法)

假设你正在爬楼梯。需要 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))

文章来源:https://blog.csdn.net/m0_73811154/article/details/135060126
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。